#pragma once

#include <iostream>
#include <vector>
#include <algorithm>
#include <hash_map>
#include "PKB.h"
#include <assert.h>

using namespace stdext;
using namespace std;

bool PKB::instanceFlag = false;
PKB* PKB::myPKB = NULL;

PKB::PKB(void) {
	myParentStarBitMapFlag = false;
	myFollowStarBitMapFlag = false;
	myCallStarBitMapFlag = false;
	commonParentSetFlag = false;
	myAST = AST();
	myFollowsTable = Follow();		
	myParentTable = Parent();
	myCallsTable = Calls();

	myModifyTable = Modifies();
	myUseTable = Uses();
	myCommonParent = CommonParent();

	myVarTable = VarTable();		
	myProcTable =ProcTable();
	myNodeTable = NodeTable();
	myConstantTable = ConstantTable();
	myEntityTable = EntityTable();

	myLastWhileMap = Type::Map::Line();
	myLastIfMap = Type::Map::Line();

	instanceFlag = true;
}

PKB* PKB::getInstance(){
	if(!instanceFlag){
		initializeInstance();
	}
	return myPKB;
}

PKB::~PKB(void){
	clear();
	myParentStarBitMapFlag = false;
	myFollowStarBitMapFlag = false;
	myCallStarBitMapFlag = false;
	commonParentSetFlag = false;
	instanceFlag = false;
}

void PKB::clear(){
	myAST = AST();
	myFollowsTable = Follow();		
	myParentTable = Parent();
	myCallsTable = Calls();

	myUseTable.clear();
	myModifyTable.clear();
	myCommonParent.clear();

	myVarTable.clear();
	myProcTable.clear();
	myNodeTable.clear();
	myConstantTable.clear();
	myEntityTable.clear();

	myLastIfMap.clear();
	myLastWhileMap.clear();
}

void PKB::initializeInstance(){
	myPKB = new PKB();
}

/****************Helper**************/
//getFirstSibling returns itself if it is the first child of it's parent
Type::Index::Line PKB::getFirstSibling(Type::Index::Line me){
	if ( !isLineExists(me)) {
		return -1;
	}
	Type::Index::Line result;
	Type::List::Line allMeFollow = getFollowedByStar(me);
	allMeFollow.push_back(me);
	result = PKB::getMin(allMeFollow);
	return result;
}
//getLastSibling returns itself if it is the last child of it's parent
Type::Index::Line PKB::getLastSibling(Type::Index::Line me){
	if ( !isLineExists(me)) {
		return -1;
	}
	Type::Index::Line result;
	Type::List::Line allFollowMe = getFollowStar(me);
	allFollowMe.push_back(me);
	result = getMax(allFollowMe);
	return result;
}

bool subTreeMatch(TreeNode a, TreeNode b){
	if (a.getNodeType() == b.getNodeType()){
		if (a.getNodeType() == AST_CONST || a.getNodeType() == AST_VAR){
			if (a.getContent()!=b.getContent()){
				return false;
			}
		}
		if (a.getChild().size()==b.getChild().size()){
			if (a.getChild().size()==0){
				return true;
			}else{
				return subTreeMatch(*a.getChild().at(0), *b.getChild().at(0))&&subTreeMatch(*a.getChild().at(1), *b.getChild().at(1));
			}
		}
	}
	return false;
}

bool subTreePartialMatch(TreeNode a, TreeNode b){
	if (subTreeMatch(a,b)){
		return true;
	}else{

		for(unsigned int i=0; i<a.getChild().size();i++){
			if (subTreePartialMatch(*a.getChild().at(i),b)){
				return true;
			}
		}
	}
	return false;
}
Type::Entity::Line patternTypeToLineEntityType(PatternType patternType){
	Type::Entity::Line lineEntity;
	switch(patternType){
	case PATTERN_WHILE:
		lineEntity = Type::Entity::WHILE_LINE_ENTITY;
		break;
	case PATTERN_IF:
		lineEntity = Type::Entity::IF_LINE_ENTITY;
		break;
	case PATTERN_ASSIGN:
		lineEntity = Type::Entity::ASSIGNMENT_LINE_ENTITY;
		break;
	default:
		lineEntity = Type::Entity::INVALID_LINE_ENTITY;
	}
	return lineEntity;
}

Type::List::Line PKB::filterLineIndexByLineEntityType(Type::List::Line listOfLines, Type::Entity::Line typeRequired){
	Type::List::Line filtedLines;
	for (Type::List::Line::iterator iter = listOfLines.begin(); iter!= listOfLines.end(); ++iter){
		if (isLineEntity(*iter, typeRequired)){
			filtedLines.push_back(*iter);
		}
	}
	return filtedLines;

}

/*************CFG*****************/
CFG* PKB::createCFG(Type::Index::Proc proc){
	assert (Utilities::isValidProcIndex(proc));
	return new CFG(proc);
}
void PKB::setCFGRoot(CFG* cfg, CFGNode* root){
	cfg->setRoot(root);
}
CFGNode* PKB::getCFGRootNode(CFG* cfg){
	return cfg->getRoot();
}
CFGNode* PKB::getCFGEndNode(CFG* cfg){
	return cfg->getEnd();
}
void PKB::addToCFGFamily(CFG* cfg){
	PKB::myCFGFamily[cfg->getProcIndexCFG()] = cfg;
}
CFG* PKB::getCFGByProcedureIndex(Type::Index::Proc p){
	if (myCFGFamily.find(p) != myCFGFamily.end()){
		return myCFGFamily.find(p)->second;
	}else{
		return NULL;
	}
}

//create CFGNode with its contents and coresponding AST node.
CFGNode* PKB::createCFGNode(Type::Index::Line l, TreeNode* tn){
	return new CFGNode(l,tn);
}
//create CFG End Node which has a content equals to -2
CFGNode* PKB::createCFGEndNode(){
	return new CFGNode();
}

//the first CFGNode will become the predecessor of the second CFGNode. and the Second CFGNode will become the successor of the first CFG Node.
bool PKB::linkCFGNodes(CFGNode* pred, CFGNode* succ){
	assert(pred);
	assert(succ);
	pred->addSuccessor(succ);
	succ->addPredecessor(pred);
	return true;
}

//get a CFGNode's corresponding ASTNode
TreeNode* PKB::getASTNodeFromCFG(CFGNode* cfgNode){
	return cfgNode->getASTNodeLink();
}
//get the content in the CFGNode. The content refers to the line index.
Type::Index::Line PKB::getCFGNodeContent(CFGNode* cfgNode){
	return cfgNode->getContent();
}

//return a list of CFGNode pointers which are the successors of given CFGNode
vector<CFGNode*> PKB::getSuccessorsCFG(CFGNode* cfgNode){
	return cfgNode->getSuccessor();
}
//return a list of CFGNode pointers which are the predecessors of given CFGNode
vector<CFGNode*> PKB::getPredecessorCFG(CFGNode* cfgNode){
	return cfgNode->getPredecessor();
}
/****************NextBip**************/
//set NextBip relation
bool PKB::setNextBip(Type::Index::Line p, Type::Index::Line s){
	assert( Utilities::isValidLineIndex(p));
	assert( Utilities::isValidLineIndex(s));
	return myNextBipTable.setNext(p,s);
}
//return a list of line which is NextBip to the given line. eg NextBip(1,2), NextBip(1,3) getSuccessorNextBip(1) will return 2,3
Type::List::Line PKB::getSuccessorNextBip(Type::Index::Line p){
	assert( Utilities::isValidLineIndex(p));
	if ( !isLineExists(p)) {
		return Type::List::Line();
	}
	//call statement
	if (isLineEntity(p, Type::Entity::CALL_LINE_ENTITY)){
		return myNextBipTable.getSuccessor(p);
	//union of nextbip and next
	}else{
		Type::List::Line result;
		Type::List::Line sucNextOfP = PKB::getSuccessorNext(p);
		if (!sucNextOfP.empty()){
			for (Type::List::Line::iterator iter = sucNextOfP.begin(); iter!=sucNextOfP.end(); ++iter){
				result.push_back(*iter);
			}
		}
		Type::List::Line sucNextBipOfS = myNextBipTable.getSuccessor(p);
		if (!sucNextBipOfS.empty()){
			for (Type::List::Line::iterator iter2 = sucNextBipOfS.begin(); iter2!=sucNextBipOfS.end(); ++iter2){
				result.push_back(*iter2);
			}
		}
		return result;
	}
}
//return a list of line which the given line is NextBip to. eg NextBip(2,4), NextBip(3,4) getPredecessorNextBip(4) will return 2,3
Type::List::Line PKB::getPredecessorNextBip(Type::Index::Line s){
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(s)) {
		return Type::List::Line();
	}
	//if it is the first line of the proc. it might be a call or what ever
	if (!PKB::hasPredecessorNext(s)){
		return myNextBipTable.getPredecessor(s);
	//it is not the first line of the proc, and its preced
	}else{
		Type::List::Line result;
		Type::List::Line preNextOfS = PKB::getPredecessorNext(s);
		if (!preNextOfS.empty()){
			for (Type::List::Line::iterator iter = preNextOfS.begin(); iter!=preNextOfS.end(); ++iter){
				if(!isLineEntity(*iter, Type::Entity::CALL_LINE_ENTITY)){
					result.push_back(*iter);
				}
			}
		}

		Type::List::Line preNextBipOfS = myNextBipTable.getPredecessor(s);
		if (!preNextBipOfS.empty()){
			for (Type::List::Line::iterator iter2 = preNextBipOfS.begin(); iter2!=preNextBipOfS.end(); ++iter2){
				result.push_back(*iter2);
			}
		}
		return result;
	}
}
//return true if the given two line index have NextBip relation. eg NextBip(1,2) isNextBip(1,2) will return true
bool PKB::isNextBip(Type::Index::Line p, Type::Index::Line s){
	assert( Utilities::isValidLineIndex(p));
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(p) || !isLineExists(s)) {
		return false;
	}
	//return myNextBipTable.isNext(p,s);
	Type::List::Line sucsOfP = PKB::getSuccessorNextBip(p);
	for(Type::List::Line::iterator iter = sucsOfP.begin(); iter != sucsOfP.end(); ++iter){
		if (*iter == s){
			return true;
		}
	}
	return false;
}
//return true if the given line index has some line that is after it
bool PKB::hasSuccessorNextBip(Type::Index::Line p){
	assert( Utilities::isValidLineIndex(p));
	if ( !isLineExists(p)) {
		return false;
	}
	//return myNextBipTable.hasSuccessor(p);
	Type::List::Line sucsOfP = PKB::getSuccessorNextBip(p);
	return !sucsOfP.empty();
}
//return true if the given line index has some line that is before it
bool PKB::hasPredecessorNextBip(Type::Index::Line s){
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(s)) {
		return false;
	}
	//return myNextBipTable.hasPredecessor(s);
	Type::List::Line predOfS = PKB::getPredecessorNextBip(s);
	return !predOfS.empty();
}
/***NextBipStar*****/
int PKB::getNumOfExitPoints(Type::Index::Proc proc){
	//shouldn't matter, since even some Colleague has gotten back to the caller and I cannot get back to the caller, 
	//the goal is still achieved. I am pushed into the list and my colleague got pushed into the list and also the caller got the return back call.
	 int count = 1;
	 if (PKB::getProcExitPoints(proc).empty()){
		count = 0;
	 }else{
		count = PKB::getProcExitPoints(proc).size();
	 }
	 return count;
}
bool PKB::isExitPoint(Type::Index::Line a){
	//std::cout<<"checking is Exit Point ? "<<a<<std::endl;
	Type::Index::Proc proc = PKB::getProcIndexOfLine(a);
	//std::cout<<"Proc of  "<<a<<" is "<<proc<<std::endl;
	//when it is a while --> if doesnot have follower and no while parent* return true else return false
	/////check no while parent*? getCommonWhile(a,parent(a))?
	if (PKB::getLineEntityByLine(a)==Type::Entity::WHILE_LINE_ENTITY){
		bool notFollowedByOthers = (PKB::getFollows(a) == -1);
		bool noWhileParent = (PKB::getParent(a) == -1) ||(PKB::getCommon(Type::Entity::WHILE_LINE_ENTITY,a,PKB::getParent(a))<=0);
		return notFollowedByOthers && noWhileParent;
	}else{
		//when a is not a while and has successorNext, return false
		//when a is not a while and does not have successorNext, then it must be the exit point. return true
		///////a call statement will never be the exit point
		//return !PKB::hasSuccessorNext(a) && (PKB::getLineEntityByLine(a)!=Type::Entity::CALL_LINE_ENTITY);
		return !PKB::hasSuccessorNext(a);
	}
}
void printAList(Type::List::Line lst){
	for(unsigned int k=0;k < lst.size();k++){
			std::cout<<lst.at(k)<<" ";
	}
	std::cout<<std::endl;
}

Type::List::Line PKB::getSuccessorNextBipStar(Type::Index::Line p){
	//return getSuccessorNextBipStar_Yude(p);
	hash_map<Type::Index::Line,bool> resultHashMap;
	int totalProc = PKB::getProcIndices().size();
	vector<bool> markOfProc (totalProc+1,false);
	Type::Index::Line procOfp = PKB::getProcIndexOfLine(p);
	//myself
	Type::List::Line results = PKB::getSuccessorNextStar(p);
	Type::List::Line callStmts;
	if (PKB::getLineEntityByLine(p)==Type::Entity::CALL_LINE_ENTITY){
			callStmts.push_back(p);
	}
	for (Type::List::Line::iterator iterR = results.begin(); iterR!=results.end(); ++iterR){
		resultHashMap[*iterR]=true;
		if ((PKB::getLineEntityByLine(*iterR)==Type::Entity::CALL_LINE_ENTITY)&&(*iterR!=p)){
			callStmts.push_back(*iterR);
		}
	}
	Type::List::Line exitsToPoints = PKB::getProcExitToIndexes(procOfp);
	
	//forward
	while (!callStmts.empty()){
		Type::Index::Line callStmt = callStmts.back();
		callStmts.pop_back();
		Type::Index::Proc procCalled = PKB::getCalledByLine(callStmt);
		if (!markOfProc.at(procCalled)){
			Type::Index::Line start = PKB::getProcStartEnd(procCalled).first;
			Type::Index::Line end = PKB::getProcStartEnd(procCalled).second;
			for (Type::Index::Line i = start; i<=end; i++){
				//all line in the proc called by me
				resultHashMap[i] = true;
				results.push_back(i);
				if (PKB::getLineEntityByLine(i)==Type::Entity::CALL_LINE_ENTITY){
					callStmts.push_back(i);				
				}
			}
			markOfProc.at(procCalled) = true;
		}
	}
	//backward
	Type::List::Line callLines;
	while (!exitsToPoints.empty()){
		Type::Index::Line exitToPoint = exitsToPoints.back();
		exitsToPoints.pop_back();

		Type::Index::Proc procOfExitToPoint = PKB::getProcIndexOfLine(exitToPoint);
		Type::List::Line deeperExitToPoints = PKB::getProcExitToIndexes(procOfExitToPoint);

		if (resultHashMap.find(exitToPoint)==resultHashMap.end()){
			resultHashMap[exitToPoint] = true;
			results.push_back(exitToPoint);
		}
		Type::List::Line sucsNextOfETP = PKB::getSuccessorNextStar(exitToPoint);
		for (Type::List::Line::iterator sucs = sucsNextOfETP.begin(); sucs!=sucsNextOfETP.end();++sucs){
			if (PKB::getLineEntityByLine(*sucs) == Type::Entity::CALL_LINE_ENTITY){
				callLines.push_back(*sucs);
			}
			if (exitToPoint != *sucs){
				if (resultHashMap.find(*sucs)==resultHashMap.end()){
					resultHashMap[*sucs] = true;
					results.push_back(*sucs);
				}
			}
		}
		exitsToPoints.insert(exitsToPoints.end(),deeperExitToPoints.begin(),deeperExitToPoints.end());
	}
	while (!callLines.empty()){
		Type::Index::Line callStmt = callLines.back();
		callLines.pop_back();
		Type::Index::Proc procCalled = PKB::getCalledByLine(callStmt);
		if (!markOfProc.at(procCalled)){
			Type::Index::Line start = PKB::getProcStartEnd(procCalled).first;
			Type::Index::Line end = PKB::getProcStartEnd(procCalled).second;
			if (procCalled==procOfp){
				for (Type::Index::Line i = start; i<=end; i++){
					//if it is my predecessor but not my successor then I will push it and push any call found
					if (!PKB::isNextStar(p,i)){
						if (resultHashMap.find(i)==resultHashMap.end()){
							resultHashMap[i] = true;
							results.push_back(i);
						}
						if (PKB::getLineEntityByLine(i)==Type::Entity::CALL_LINE_ENTITY){
							callLines.push_back(i);				
						}
					}
				}
			}else{
				for (Type::Index::Line i = start; i<=end; i++){
					//all line in the proc called by me
					//results.push_back(i);
					if (resultHashMap.find(i)==resultHashMap.end()){
						resultHashMap[i] = true;
						results.push_back(i);
					}
					if (PKB::getLineEntityByLine(i)==Type::Entity::CALL_LINE_ENTITY){
						callLines.push_back(i);				
					}
				}
				
			}
			markOfProc.at(procCalled) = true;
		}
	}
	return results;
}

/// Written by Yu De. Returns a list of line which are on the control flow after given line
Type::List::Line PKB::getSuccessorNextBipStar_Yude(Type::Index::Line line) {
	/*---------------------------------------------------------------
	 *	Algorithm:
	 *	Simply traverse the nextBIP graph from the given line,
	 *	and add all the successors.
	 *	Important point, however, is that whenever the current line 
	 *	is either an exit point, we must check all its
	 *	successors and ensure that isNextBipStar(line, successor) is
	 *	true and only add those successors which are true.
	 *	Although this method may be slightly slower, the checking is
	 *	only done O(c) times, and the isNextBipStar check is O(c).
	 *	Therefore the total complexity is just O(n + c), where n is
	 *	the number of statements in a program, and c is the number of
	 *	call statements in a program.
	 *---------------------------------------------------------------*/
	Type::List::Line results; // to be returned
	if ( !isLineExists(line)) {
		return results;
	}

	std::unordered_map<Type::Index::Line, bool> resultsMap; // for unique indexes only

	// First, get all the exit points of all procs and insert it into the exitPointskMap
	std::unordered_map<Type::Index::Line, bool> exitPointsMap;
	const Type::List::Proc& procList = getProcIndices();
	for (auto procIt = procList.begin(); procIt != procList.end(); procIt++) {
		Type::List::Line exitPoints = getProcExitPoints(*procIt);
		for (auto exitPoint = exitPoints.begin(); exitPoint != exitPoints.end(); exitPoint++) {
			exitPointsMap.insert( std::make_pair(*exitPoint, true) );
		}
	}

	// Now, we are ready to start traversing the nextBIP graph.
	// Start it rolling!
	Type::List::Line successorBipList = getSuccessorNextBip(line);
	// Add all the results into the resultsMap as well so as to get only unique indexes
	bool needToCheckNextBipStar = Utilities::isKeyInMap_TypeType(exitPointsMap, line);
	for (unsigned int i = 0; i < successorBipList.size(); i++) {
		Type::Index::Line successorBip = successorBipList.at(i);
		bool isGoodToAdd = true;
		if (needToCheckNextBipStar && !isNextBipStar(line, successorBip)) {
			isGoodToAdd = false;
		}
		if (isGoodToAdd) {
			results.push_back(successorBip);
			resultsMap.insert( std::make_pair(successorBip, true) );
		}
	}
	
	// Traverse nextBIP graph!
	for (unsigned int i = 0; i < results.size(); i++) {
		Type::Index::Line currentLine = results.at(i);
		// Need to check next bip star if the current line is an exit point.
		bool needToCheckNextBipStar = Utilities::isKeyInMap_TypeType(exitPointsMap, currentLine);
		Type::List::Line nextBipList = getSuccessorNextBip(currentLine);
		for (auto nextBipIt = nextBipList.begin(); nextBipIt != nextBipList.end(); nextBipIt++) {
			if ( !Utilities::isKeyInMap_TypeType(resultsMap, *nextBipIt)) {
				// Not added before
				bool isGoodToAdd = true;
				if (needToCheckNextBipStar && !isNextBipStar(line, *nextBipIt)) {
					isGoodToAdd = false;
				}
				if (isGoodToAdd) {
					results.push_back(*nextBipIt);
					resultsMap.insert( std::make_pair(*nextBipIt, true) );
				}
			}
		}
	}

	return results;
}

//return a list of line which are on the control flow before given line
Type::List::Line PKB::getPredecessorNextBipStar(Type::Index::Line s){
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(s)) {
		return Type::List::Line();
	}
	Type::List::Line predecessorsTotal;
	getNextStarHelper(s, &predecessorsTotal, &PKB::getPredecessorNextBip, this, true);
	return predecessorsTotal;
}

bool PKB::isNextBipStar(Type::Index::Line a, Type::Index::Line b){
	assert( Utilities::isValidLineIndex(a));
	assert( Utilities::isValidLineIndex(b));
	if ( !isLineExists(a) || !isLineExists(b)) {
		return false;
	}
	return hasOutRoute(a, b, 0);
	//Type::Index::Proc procOfA = PKB::getProcIndexOfLine(a);
	//Type::Index::Proc procOfB = PKB::getProcIndexOfLine(b);
	//std::cout<<"a "<<a<<" b "<<b<<std::endl;
	//std::cout<<"proc a "<<procOfA<<"proc b "<<procOfB<<std::endl;
	//if (procOfA == procOfB){
	//	std::cout<<"procOfA is same as procOfB"<<std::endl;
	//	if (PKB::isNextStar(a,b)){
	//		return true;
	//	}else{
	//		if (PKB::getCallerOf(procOfA).empty()){
	//			return false;
	//		}
	//		std::cout<<"a b not nextStar"<<std::endl;
	//		Type::List::Line exitToPoints = PKB::getProcExitToIndexes(procOfA);
	//		bool flagOfOr = false;
	//		for (Type::List::Line::iterator iterE = exitToPoints.begin();iterE!=exitToPoints.end();++iterE){
	//			std::cout<<"procOfA's exitToPoints "<<*iterE<<std::endl;
	//			flagOfOr = (flagOfOr||isNextBipStar(*iterE,b));
	//			if (flagOfOr){
	//				return true;
	//			}
	//		}
	//		return false;
	//	}
	//}else if(!PKB::isCallsStar(procOfA,procOfB)&&!PKB::isCallsStar(procOfB,procOfA)){
	//	//no link between them
	//	return false;
	//}else{
	//	if (PKB::isCallsStar(procOfA,procOfB)){
	//		std::cout<<"procOfA callstar procOfB"<<std::endl;
	//		//procOfA callstar procOfB
	//		//i want to find a line in proc a that callstar procOfB and a is before this line(isNextStar(a,thisline))
	//		Type::List::Line sucsOfa = PKB::getSuccessorNext(a);
	//		hash_map<Type::Index::Line,bool> markSucsOfa;
	//		//in case a itself is a call statement
	//		sucsOfa.push_back(a);
	//		for (int i=0; i<sucsOfa.size();i++){
	//			markSucsOfa[sucsOfa.at(i)]=true;
	//		}
	//		Type::List::Line sucsBipOfa = PKB::getSuccessorNextBip(a);
	//		for (Type::List::Line::iterator sucBipOfa = sucsBipOfa.begin(); sucBipOfa!=sucsBipOfa.end();++sucBipOfa){
	//			if (markSucsOfa.find(*sucBipOfa)==markSucsOfa.end()){
	//				sucsOfa.push_back(*sucBipOfa);
	//				markSucsOfa[*sucBipOfa]=true;
	//			}
	//		}
	//		while (!sucsOfa.empty()){
	//			std::cout<<"sucOfa list"<<std::endl;
	//			printAList(sucsOfa);
	//			Type::Index::Line sucOfa = sucsOfa.front();
	//			std::cout<<"sucOfa is "<<sucOfa<<std::endl;
	//			sucsOfa.erase(sucsOfa.begin());
	//			if (PKB::getLineEntityByLine(sucOfa)==Type::Entity::CALL_LINE_ENTITY){
	//				std::cout<<"sucOfa is a call"<<std::endl;
	//				Type::Index::Proc calledProc = PKB::getCalledByLine(sucOfa);
	//				std::cout<<"proc called by sucOfa is "<<calledProc<<std::endl;
	//				std::cout<<"reminder procOfB is "<<procOfB<<endl;
	//				if (calledProc==procOfB||PKB::isCallsStar(calledProc, procOfB)){
	//					return true;
	//				}
	//				std::cout<<"this predeOfb is not a call star line to procOfA";
	//			}
	//			Type::List::Line deeperSucOfa = PKB::getSuccessorNext(sucOfa);
	//			for (Type::List::Line::iterator iterDeepSuc = deeperSucOfa.begin(); iterDeepSuc!=deeperSucOfa.end();++iterDeepSuc){
	//				if (markSucsOfa.find(*iterDeepSuc)==markSucsOfa.end()){
	//					sucsOfa.push_back(*iterDeepSuc);
	//					markSucsOfa[*iterDeepSuc]=true;
	//				}
	//			}
	//			/*Type::List::Line deeperSucsBipOfa = PKB::getSuccessorNextBip(sucOfa);
	//			for (Type::List::Line::iterator iterDeepSucBip = deeperSucsBipOfa.begin(); iterDeepSucBip!=deeperSucsBipOfa.end();++iterDeepSucBip){
	//				if (markSucsOfa.find(*iterDeepSucBip)==markSucsOfa.end()){
	//					sucsOfa.push_back(*iterDeepSucBip);
	//					markSucsOfa[*iterDeepSucBip]=true;
	//				}
	//			}*/
	//		}
	//		return false;
	//	}else{
	//		std::cout<<"procOfB callstar procOfA"<<std::endl;
	//		//procOfB callstar procOfA
	//		//i want to find which line in procOfB that callstar procOfA and check if b is after this line(isNextStar(thisline,b))
	//		Type::List::Line predesOfb = PKB::getPredecessorNext(b);
	//		
	//		hash_map<Type::Index::Line,bool> markpredesOfb;
	//		for (int i=0; i<predesOfb.size();i++){
	//			markpredesOfb[predesOfb.at(i)]=true;
	//		}
	//		Type::List::Line predesBipOfb = PKB::getPredecessorNextBip(b);
	//		for (Type::List::Line::iterator preBipOfb = predesBipOfb.begin(); preBipOfb!=predesBipOfb.end();++preBipOfb){
	//			if (markpredesOfb.find(*preBipOfb)==markpredesOfb.end()){
	//				predesOfb.push_back(*preBipOfb);
	//				markpredesOfb[*preBipOfb]=true;
	//			}
	//		}
	//		std::cout<<"predesOfb the list "<<std::endl;
	//		printAList(predesOfb);
	//		
	//		while (!predesOfb.empty()){
	//			std::cout<<"predesOfb the list "<<std::endl;
	//			printAList(predesOfb);
	//			Type::Index::Line predeOfb = predesOfb.front();
	//			std::cout<<"predeOfb "<<predeOfb<<std::endl;
	//			//predesOfb.pop_back();
	//			predesOfb.erase(predesOfb.begin());
	//			if (PKB::getLineEntityByLine(predeOfb)==Type::Entity::CALL_LINE_ENTITY){
	//				std::cout<<"predeOfb is call"<<std::endl;
	//				Type::Index::Proc calledProc = PKB::getCalledByLine(predeOfb);
	//				std::cout<<"the proc called by this predeOfb is "<<calledProc<<std::endl;
	//				std::cout<<"reminder procOfA is "<<procOfA<<std::endl;
	//				if (calledProc==procOfA||PKB::isCallsStar(calledProc,procOfA)){
	//					return true;
	//				}
	//				std::cout<<"this predeOfb is not a call star line to procOfA";
	//			}
	//			Type::List::Line deeperPredeOfb = PKB::getPredecessorNext(predeOfb);
	//			for (Type::List::Line::iterator iterDeep = deeperPredeOfb.begin(); iterDeep!=deeperPredeOfb.end();++iterDeep){
	//				if (markpredesOfb.find(*iterDeep)==markpredesOfb.end()){
	//					predesOfb.push_back(*iterDeep);
	//					markpredesOfb[*iterDeep]=true;
	//				}
	//			}
	//			Type::List::Line deeperPredeBipOfb = PKB::getPredecessorNextBip(predeOfb);
	//			for (Type::List::Line::iterator iterDeepBip = deeperPredeBipOfb.begin(); iterDeepBip!=deeperPredeBipOfb.end();++iterDeepBip){

	//				if (markpredesOfb.find(*iterDeepBip)==markpredesOfb.end()){
	//					predesOfb.push_back(*iterDeepBip);
	//					markpredesOfb[*iterDeepBip]=true;
	//				}
	//			}
	//			std::cout<<"predesOfb the list end of a while"<<std::endl;
	//			printAList(predesOfb);
	//		}
	//		return false;
	//	}
	//}
}

bool PKB::setNextBipBitMap(Type::Map::Bit CBM){
	return myNextBipTable.setNextBitMap(CBM);
}

bool PKB::isNextBipBitMapSet(){
	return myNextBipTable.isBitMapSet();
}

/****************Next**************/
bool PKB::setNext(Type::Index::Line p, Type::Index::Line s){
	assert( Utilities::isValidLineIndex(p));
	assert( Utilities::isValidLineIndex(s));
	return myNextTable.setNext(p,s);
}
Type::List::Line PKB::getSuccessorNext(Type::Index::Line p){
	assert( Utilities::isValidLineIndex(p));
	if ( !isLineExists(p)) {
		return Type::List::Line();
	}
	return myNextTable.getSuccessor(p);
}
Type::List::Line PKB::getPredecessorNext(Type::Index::Line s){
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(s)) {
		return Type::List::Line();
	}
	return myNextTable.getPredecessor(s);
}
bool PKB::isNext(Type::Index::Line p, Type::Index::Line s){
	assert( Utilities::isValidLineIndex(p));
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(p) || !isLineExists(s)) {
		return false;
	}
	return myNextTable.isNext(p,s);
}
bool PKB::hasSuccessorNext(Type::Index::Line p){
	assert( Utilities::isValidLineIndex(p));
	if ( !isLineExists(p)) {
		return false;
	}
	return myNextTable.hasSuccessor(p);
}
bool PKB::hasPredecessorNext(Type::Index::Line s){
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(s)) {
		return false;
	}
	return myNextTable.hasPredecessor(s);
}

void PKB::getNextStarHelper(int p, vector<int> *childTotal, vector<int> (PKB::*innerFunction)(int), PKB* mypkb, bool self){
	vector<int>::iterator iter;
	vector<int>  child = (mypkb->*innerFunction)(p);
	for (iter = child.begin(); iter != child.end(); iter++){
		//if this child is not explored
		if (!Utilities::isExistInList(*childTotal,*iter)){
			if (*iter==p){
				if (self){
					childTotal->push_back(p);
				}
			}else{
				childTotal->push_back(*iter);
				getNextStarHelper(*iter,childTotal,innerFunction, mypkb,self);
			}
		}
	}
}

Type::List::Line PKB::getSuccessorNextStar(Type::Index::Line p){
	assert( Utilities::isValidLineIndex(p));
	if ( !isLineExists(p)) {
		return Type::List::Line();
	}
	Type::List::Line successorsTotal;
	getNextStarHelper(p, &successorsTotal, &PKB::getSuccessorNext, this, true);
	return successorsTotal;
}
Type::List::Line PKB::getPredecessorNextStar(Type::Index::Line s){
	assert( Utilities::isValidLineIndex(s));
	if ( !isLineExists(s)) {
		return Type::List::Line();
	}
	Type::List::Line predecessorsTotal;
	getNextStarHelper(s, &predecessorsTotal, &PKB::getPredecessorNext, this, true);
	return predecessorsTotal;
}
Type::Index::Line PKB::getMin(Type::List::Line list){
	//list is not null
	assert(!list.empty());
	Type::Index::Line result = list.at(0);
	for (std::vector<int>::iterator it = list.begin() ; it != list.end(); ++it){
		if (*it < result){
			result = *it;
		}
	}
	return result;
}
Type::Index::Line PKB::getMax(Type::List::Line list){
	//list is not null
	assert(!list.empty());
	Type::Index::Line result = list.at(0);
	for (std::vector<int>::iterator it = list.begin() ; it != list.end(); ++it){
		if (*it > result){
			result = *it;
		}
	}
	return result;
}
bool PKB::isCommExist(Type::List::Line listA, Type::List::Line listB){
	if (listA.empty()||listB.empty()){
		return false;
	}
	Type::Index::Line a = PKB::getMin(listA);
	Type::Index::Line b = PKB::getMin(listB);
	return a==b;
}

/**!
ASSUME the two list are sorted and no duplicate in each lists
RETURN a vector of size 3
0. the largest common value
1. the index of the largest common value in the first list
2. the index of the largest common value in the second list
if no common value (their common parent is the procedure)
0. -1
1. -1
2. -1
*/
vector<int> getLargestCommValue(Type::List::Line listA, Type::List::Line listB){
	int resultC[] = {-1,-1,-1};
	//If they are different in the beginning they wont have common in the later part. Special property for SPA
	int a = listA.size() > listB.size()? listB.size() : listA.size();
	for (int i=0; i < a; i++){
		//can improve to log n by checking at which point a != b
		if (listA.at(i) == listB.at(i)){
			//always keep the most recent correct one
			resultC[0] = listA.at(i);
			resultC[1] = i;
			resultC[2] = i;
		}else{
			vector<int> result (resultC, resultC + sizeof(resultC)/sizeof(int));
			return result;
		}
	}
	vector<int> result (resultC, resultC + sizeof(resultC)/sizeof(int));
	return result;
}

bool PKB::isNextStar(Type::Index::Line a, Type::Index::Line b){
	if ( !isLineExists(a) || !isLineExists(b)) {
		return false;
	} 
	if (commonParentSetFlag){
		return isNextStarFast(a,b);
	}else{
		return isNextStarSlow(a,b);
	}
}
bool PKB::isNextStarFast(Type::Index::Line a, Type::Index::Line b){
	assert( Utilities::isValidLineIndex(a));
	assert( Utilities::isValidLineIndex(b));
	Type::Index::Proc aInProc = PKB::getProcIndexOfLine(a);
	Type::Index::Proc bInProc = PKB::getProcIndexOfLine(b);
	if (aInProc != bInProc){
		return false;
	}
	/*******new algo with CommonParent.h*************/
	if (PKB::isNext(a,b)){ 
		return true;
	}else{
		//if common while parent
		Type::Index::Line parentOfA = PKB::getParent(a);
		Type::Index::Line parentOfB = PKB::getParent(b);
		Type::Index::Line commonWhileParent;
		if (isLineEntity(a, Type::Entity::WHILE_LINE_ENTITY)){
			parentOfA = a;
		}
		if (isLineEntity(b, Type::Entity::WHILE_LINE_ENTITY)){
			parentOfB = b;
		}
		if (parentOfA == -1 ||parentOfB == -1){
			commonWhileParent = 0;
		}else{
			commonWhileParent = PKB::getCommon(Type::Entity::WHILE_LINE_ENTITY, parentOfA, parentOfB);
		}
		/*Type::List::Line parentsA = PKB::getParentStar(a);
		Type::List::Line parentsB = PKB::getParentStar(b);
		
		for (int i=0; i<parentsA.size(); i++){
			std::cout<<parentsA.at(i)<<" ";
		}
		for (int i=0; i<parentsB.size(); i++){
			std::cout<<parentsB.at(i)<<" ";
		}*/
		if (commonWhileParent > 0){
			return true;
		}else{
		//no common while parent
			if (a >= b){
				return false;
			}else{
				//a in then, b in else
				//find the largest common parent

				Type::Index::Line parentOfA2 = PKB::getParent(a);
				Type::Index::Line parentOfB2 = PKB::getParent(b);
				Type::Index::Line commonIfParent;
				
				if (isLineEntity(a, Type::Entity::WHILE_LINE_ENTITY) || isLineEntity(a, Type::Entity::IF_LINE_ENTITY)){
					parentOfA2 = a;
				}
				if (isLineEntity(b, Type::Entity::WHILE_LINE_ENTITY) || isLineEntity(b, Type::Entity::IF_LINE_ENTITY)){
					parentOfB2 = b;
				}

				if (parentOfA2 == -1 ||parentOfB2 == -1){
					commonIfParent = 0;
				}else{
					if (parentOfA2 == parentOfB2){
						commonIfParent = parentOfA2;
					}else{
						commonIfParent = getCommon(Type::Entity::IF_LINE_ENTITY, parentOfA2, parentOfB2);
					}
				}
				//there is common if parent
				if (commonIfParent > 0){
					if (commonIfParent == a){
						return true;
					//check if they in then or else list
					}else{
						Type::List::Line nextToIf = getSuccessorNext(commonIfParent);
						/*std::cout<<std::endl<<"a "<<a<<" b "<<b<<" a&b's commonifparent is ";
						std::cout<<commonIfParent<<" "<<"size of nextToIf is "<<nextToIf.size()<<std::endl;*/
						for (Type::List::Line::iterator iter = nextToIf.begin(); iter != nextToIf.end(); ++iter){
							//std::cout<<*iter<<" ";
						}
						//std::cout<<std::endl;
						
						assert(nextToIf.size() == 2);
						//If CFG node can only have two outgoing egdes. Thus the first line in else stmt list is the largest one.
						Type::Index::Line firstOfElse = getMax(nextToIf);

						//a in then, b in else
						//it is not possible to have b in then a in else, cause a < b
						return !(a < firstOfElse && b >= firstOfElse);
					}
				//if no common parent and a < b and they are in same procedure
				}else{
					return true;
				}
			}
		}
	}
}
bool PKB::isNextStarSlow(Type::Index::Line a, Type::Index::Line b){
	assert( Utilities::isValidLineIndex(a));
	assert( Utilities::isValidLineIndex(b));
	/*Type::List::Line  successorsList;
	successorsList = PKB::getSuccessorNextStar(a);
	return Utilities::isExistInList(successorsList,b);*/
	/*******new algo*************/
	//if a in the first level This will introduce a problem when a and b are not in the same procedure
	/*if (!PKB::hasParent(a)){
		return a<=b;
	}*/
	if (isNext(a,b)){ 
		return true;
	}else{
		//if common while parent
		Type::List::Line parentStarWhileA = PKB::getParentStar(a,Type::Entity::WHILE_LINE_ENTITY);
		Type::List::Line parentStarWhileB = PKB::getParentStar(b,Type::Entity::WHILE_LINE_ENTITY);
		if (isLineEntity(a, Type::Entity::WHILE_LINE_ENTITY)){
			parentStarWhileA.push_back(a);
		}
		if (isLineEntity(b, Type::Entity::WHILE_LINE_ENTITY)){
			parentStarWhileB.push_back(b);
		}
		if (isCommExist(parentStarWhileA,parentStarWhileB)){
			return true;
		}else{
		//no common while parent
			if (a >= b){
				return false;
			}else{
				//a in then, b in else
				//find the largest common parent
				
				Type::List::Line parentStarA = getParentStar(a);
				Type::List::Line parentStarB = getParentStar(b);
				
				parentStarA.push_back(a);
				parentStarB.push_back(b);
				
				std::sort(parentStarA.begin(), parentStarA.begin()+parentStarA.size());
				std::sort(parentStarB.begin(), parentStarB.begin()+parentStarB.size());
				vector<int> result = getLargestCommValue(parentStarA,parentStarB);
				assert(result.size() == 3);
				Type::Index::Line largestCommParent = result.at(0);
				int indexInListA = result.at(1);
				int indexInListB = result.at(2);

				if (largestCommParent == a){
					//a is b's parent*
					return true;
				}
				
				//else to get the one next to the largest comm in both list then check if they follow. if yes then true else false;
				//"the next to the largest comm" is the one level deeper parent of a and b. 
				Type::Index::Line nextToLargestCommA = parentStarA.at(indexInListA+1);
				Type::Index::Line nextToLargestCommB = parentStarB.at(indexInListB+1);
				return isFollowStar(nextToLargestCommA, nextToLargestCommB);
			}
		}
	}
}
bool PKB::setNextBitMap(Type::Map::Bit CBM){
	return myNextTable.setNextBitMap(CBM);
}
bool PKB::isNextBitMapSet(){
	return myNextTable.isBitMapSet();
}
/****************AST**************/

//create TreeNode* which only has a type, like "stmtLst", "+". 
TreeNode* PKB::createTreeNode(TreeNodeType t){
	return myAST.createTreeNode(t);
}
//create TreeNode* which has a type and content. The content is the index of the a stmt or var.
TreeNode* PKB::createTreeNode(TreeNodeType t, int c){
	return myAST.createTreeNode(t,c);
}

void PKB::setRoot(TreeNode* node){
	myAST.setRoot(node);
}
TreeNode* PKB::getRoot(){
	return myAST.getRoot();
}

//add the second TreeNode* as the child of the first TreeNode*
//and add the first TreeNode* as parent of the second TreeNode*
void PKB::linkNodes(TreeNode* p,TreeNode* c){
	myAST.linkNodes(p,c);
}
void PKB::linkNodesFront(TreeNode* p,TreeNode* c){
	myAST.linkNodesFront(p,c);
}

//return true is the type of TreeNode* matches with the given TreeNode*
bool PKB::matchesNodeType(TreeNode* node, TreeNodeType t){
	return myAST.matchesNodeType(node,t);
}

//return the content inside the node
int PKB::getContentStoredIn(TreeNode* node){
	return myAST.getContentStoredIn(node);
}

//return a list of LineIndex that match the pattern type, varRefIndex and subtree partially or fully
//in the entire program
Type::List::Line PKB::getLineIndexForPattern(PatternType patternType, Type::Index::Var varRefIndex, TreeNode* rootSubTree, bool isPartial){
	// Yude's method
	return getLineIndexesForPattern(patternType, varRefIndex, rootSubTree, NULL, isPartial, true);
	Type::List::Line matchedProgLines;
	Type::Entity::Line lineEntityType = patternTypeToLineEntityType(patternType);
	Type::List::Line matchPatternLines = getLinesByEntity(lineEntityType);
	for (unsigned int i=0; i<matchPatternLines.size(); i++){

		Type::Index::Line lineIndex  = matchPatternLines.at(i);
		TreeNode* mPatternNodePointer = myNodeTable.getNodeByLine(lineIndex);
		TreeNode* varRefNode = mPatternNodePointer->getChild().at(0);

		if (varRefIndex == NULL || (varRefNode->getContent() == varRefIndex)){
			switch(patternType){
			case PATTERN_WHILE:
				//no need to check
				if (mPatternNodePointer->getNodeType() == AST_WHILE){
					matchedProgLines.push_back(matchPatternLines.at(i));
				}
				break;
			case PATTERN_IF:
				if (mPatternNodePointer->getNodeType() == AST_IF){
					matchedProgLines.push_back(matchPatternLines.at(i));
				}
				break;
			case PATTERN_ASSIGN:
				if (mPatternNodePointer->getChild().size()>1&&mPatternNodePointer->getNodeType() == AST_ASSIGN){	
					if (rootSubTree == NULL){
						matchedProgLines.push_back(matchPatternLines.at(i));
					}else{
						TreeNode expressionNode = *mPatternNodePointer->getChild().at(1);
						if (isPartial){
							if (subTreePartialMatch(expressionNode, *rootSubTree)){
								matchedProgLines.push_back(matchPatternLines.at(i));
							}
						}else{
							if (subTreeMatch(expressionNode, *rootSubTree)){
								matchedProgLines.push_back(matchPatternLines.at(i));
							}
						}
					}
				}
				break;
			default:
				break;
			}
		}
	}
	return matchedProgLines;
}

/****************ConstantTable**************/

bool PKB::insertConstant(Type::Index::Line line, Type::Entity::Line entity, Type::Constant con){
	return myConstantTable.insertConstant(line, entity, con);
}

const Type::List::Constant& PKB::getConstants(){
	return myConstantTable.getConstants();
}

const Type::List::Constant& PKB::getConstantsAtLine(Type::Index::Line line){
	return myConstantTable.getConstantsByLine(line);
}

const Type::List::Line& PKB::getLinesOfConstant(Type::Constant con){
	return myConstantTable.getLinesByConstant(con);
}

const Type::List::Line& PKB::getLinesOfConstant(Type::Constant con, Type::Entity::Line entity){
	return myConstantTable.getLinesByConstant(con, entity);
}

bool PKB::isConstantExists(Type::Constant con){
	return myConstantTable.isConstantExistsInLine(con);
}

/****************VarTable**************/

Type::Index::Var PKB::insertVar(Type::Name::Var varName){
	return myVarTable.insertVar(varName);
}

const Type::List::Var& PKB::getVarIndices(){
	return myVarTable.getVarIndices();
}

Type::Index::Var PKB::getVarIndex(Type::Name::Var varName){
	return myVarTable.getVarIndex(varName);
}

Type::Name::Var PKB::getVarName(Type::Index::Var varIndex){
	return myVarTable.getVarName(varIndex);
}

bool PKB::isVarExists(Type::Name::Var varName){
	return myVarTable.isVarExistsInVarTable(varName);
}

bool PKB::isVarExists(Type::Index::Var varIndex){
	return myVarTable.isVarExistsInVarTable(varIndex);
}

/****************ProcTable**************/

Type::Index::Proc PKB::insertProc(Type::Name::Proc procName){
	return myProcTable.insertProc(procName);
}

bool PKB::insertProcStartEnd(Type::Index::Proc proc, Type::Index::Line start, Type::Index::Line end){
	return myProcTable.insertProcStartEnd(proc, start, end);
}

const Type::List::Proc& PKB::getProcIndices(){
	return myProcTable.getProcIndices();
}

Type::Index::Proc PKB::getProcIndex(Type::Name::Proc procName){
	return myProcTable.getProcIndex(procName);
}

Type::Name::Proc PKB::getProcName(Type::Index::Proc procIndex){
	return myProcTable.getProcName(procIndex);
}

Type::Pair::StartEnd PKB::getProcStartEnd(Type::Index::Proc proc){
	return myProcTable.getProcStartEnd(proc);
}

Type::Index::Proc PKB::getProcIndexOfLine(Type::Index::Line line){
	return myProcTable.getProcIndexOfLine(line);
}

bool PKB::isProcExistInProcTable(Type::Name::Proc procName){
	return myProcTable.isProcExistsInProcTable(procName);
}

bool PKB::isProcExistInProcTable(Type::Index::Proc procIndex){
	return myProcTable.isProcExistsInProcTable(procIndex);
}

bool PKB::setProcExitPoint(Type::Index::Proc proc, Type::Index::Line point){
	return myProcTable.setProcExitPoint(proc, point);
}

const Type::List::Line& PKB::getProcExitPoints(Type::Index::Proc proc){
	return myProcTable.getProcExitPoints(proc);
}

/****************EntityTable**************/

bool PKB::insertLineEntity(Type::Index::Line line, Type::Entity::Line entity){
	return myEntityTable.insertLineEntity(line, entity);
}

bool PKB::setLastOfWhile(Type::Index::Line lineOfWhile, Type::Index::Line lastLine){
	if(!Utilities::isValidLineIndex(lineOfWhile) || !Utilities::isValidLineIndex(lastLine)
		|| !isLineEntity(lineOfWhile, Type::Entity::WHILE_LINE_ENTITY) || lineOfWhile >= lastLine){
		return false;
	}

	Type::List::Line lines;
	lines.push_back(lastLine);
	return setLastLineOfContainer(Type::Entity::WHILE_LINE_ENTITY, lineOfWhile, lines);
}

bool PKB::setLastOfIf(Type::Index::Line lineOfIf, Type::Index::Line lastLineOfThen, Type::Index::Line lastLineOfElse){
	if(!Utilities::isValidLineIndex(lineOfIf) || !Utilities::isValidLineIndex(lastLineOfThen)
		|| !Utilities::isValidLineIndex(lastLineOfElse) || !isLineEntity(lineOfIf, Type::Entity::IF_LINE_ENTITY)
		|| lineOfIf >= lastLineOfThen || lineOfIf >= lastLineOfElse){
		return false;
	}

	Type::List::Line lines;
	lines.push_back(lastLineOfThen);
	lines.push_back(lastLineOfElse);
	return setLastLineOfContainer(Type::Entity::IF_LINE_ENTITY, lineOfIf, lines);
}

bool PKB::setLastLineOfContainer(Type::Entity::Line entity, Type::Index::Line lineOfContainer, Type::List::Line& last){
	Type::Map::Line* containerMap;

	if(entity == Type::Entity::IF_LINE_ENTITY){
		containerMap = &myLastIfMap;
	}else{
		containerMap = &myLastWhileMap;
	}

	// last line of the container statement does not exist in the map
	if(containerMap->find(lineOfContainer) == containerMap->end()){
		containerMap->insert(std::make_pair<Type::Index::Line, Type::List::Line>(lineOfContainer, last));
		return true;
	}
	else{
		// last line of while has been set before
		return false;
	}
}

const Type::List::LineEntity& PKB::getLineEntities(){
	return myEntityTable.getLineEntities();
}

Type::Entity::Line PKB::getLineEntityByLine(Type::Index::Line line){
	return myEntityTable.getLineEntityByLine(line);
}

const Type::List::Line& PKB::getLines(){
	return myEntityTable.getLines();
}

const Type::List::Line& PKB::getLinesByEntity(Type::Entity::Line entity){
	return myEntityTable.getLinesByEntity(entity);
}

Type::Index::Line PKB::getLastOfWhile(Type::Index::Line lineOfWhile){
	if(!Utilities::isValidLineIndex(lineOfWhile) || !isLineEntity(lineOfWhile, Type::Entity::WHILE_LINE_ENTITY)){
		return -1;
	}

	if(myLastWhileMap.find(lineOfWhile) != myLastWhileMap.end()){
		return myLastWhileMap.at(lineOfWhile).front();
	}else{
		return -1;
	}
}

const Type::List::Line& PKB::getLastOfIf(Type::Index::Line lineOfIf){
	if(!Utilities::isValidLineIndex(lineOfIf) || !isLineEntity(lineOfIf, Type::Entity::IF_LINE_ENTITY)){
		return *(new Type::List::Line());
	}

	if(myLastIfMap.find(lineOfIf) != myLastIfMap.end()){
		return myLastIfMap.at(lineOfIf);
	}else{
		return *(new Type::List::Line());
	}
}

bool PKB::isLineEntity(Type::Index::Line line, Type::Entity::Line entity){
	return myEntityTable.isLineEntity(line, entity);
}

/*************************NodeTable********************************/

bool PKB::insertNode(Type::Index::Line line, TreeNode *node){
	return myNodeTable.insertNode(line, node);
}

TreeNode* PKB::getNodeByLine(Type::Index::Line line){
	return myNodeTable.getNodeByLine(line);
}

Type::Index::Line PKB::getLineByNode(TreeNode* node){
	return myNodeTable.getLineByNode(node);
}

/****************Modifies**************/

bool PKB::setLineModifies(Type::Index::Line line, Type::Entity::Line entity, Type::Index::Var var){
	return myModifyTable.setLineModifies(line, entity, var);
}

bool PKB::setProcModifies(Type::Index::Proc proc, Type::Index::Var var){
	return myModifyTable.setProcModifies(proc, var);
}

bool PKB::setLineModifiesBitMap(Type::Map::Bit bitmap){
	return myModifyTable.setLineModifiesBitMap(bitmap);
}

bool PKB::setProcModifiesBitMap(Type::Map::Bit bitmap){
	return myModifyTable.setProcModifiesBitMap(bitmap);
}

const Type::List::Var& PKB::getModifiedVars(){
	return myModifyTable.getModifiedVars();
}

const Type::List::Var& PKB::getModifiedVarsByLine(Type::Index::Line line){
	return myModifyTable.getModifiedVarsByLine(line);
}

const Type::List::Var& PKB::getModifiedVarsByProc(Type::Index::Proc proc){
	return myModifyTable.getModifiedVarsByProc(proc);
}

const Type::List::Line& PKB::getLinesModify(Type::Index::Var var){
	return myModifyTable.getLinesModify(var);
}

const Type::List::Line& PKB::getLinesModify(Type::Index::Var var, Type::Entity::Line entity){
	return myModifyTable.getLinesModify(var, entity);
}

const Type::List::Proc& PKB::getProcsModify(Type::Index::Var var){
	return myModifyTable.getProcsModify(var);
}

bool PKB::isLineModifies(Type::Index::Line line, Type::Index::Var var){
	return myModifyTable.isLineModifies(line, var);
}

bool PKB::isProcModifies(Type::Index::Proc proc, Type::Index::Var var){
	return myModifyTable.isProcModifies(proc, var);
}

/****************Uses**************/

bool PKB::setLineUses(Type::Index::Line line, Type::Entity::Line entity, Type::Index::Var var){
	return myUseTable.setLineUses(line, entity, var);
}

bool PKB::setProcUses(Type::Index::Proc proc, Type::Index::Var var){
	return myUseTable.setProcUses(proc, var);
}

bool PKB::setLineUsesBitMap(Type::Map::Bit bitmap){
	return myUseTable.setLineUsesBitMap(bitmap);
}

bool PKB::setProcUsesBitMap(Type::Map::Bit bitmap){
	return myUseTable.setProcUsesBitMap(bitmap);
}

const Type::List::Var& PKB::getUsedVars(){
	return myUseTable.getUsedVars();
}

const Type::List::Var& PKB::getUsedVarsByLine(Type::Index::Line line){
	return myUseTable.getUsedVarsByLine(line);
}

const Type::List::Var& PKB::getUsedVarsByProc(Type::Index::Proc proc){
	return myUseTable.getUsedVarsByProc(proc);
}

const Type::List::Line& PKB::getLinesUse(Type::Index::Var var){
	return myUseTable.getLinesUse(var);
}

const Type::List::Line& PKB::getLinesUse(Type::Index::Var var, Type::Entity::Line entity){
	return myUseTable.getLinesUse(var, entity);
}

const Type::List::Proc& PKB::getProcsUse(Type::Index::Var var){
	return myUseTable.getProcsUse(var);
}

bool PKB::isLineUses(Type::Index::Line line, Type::Index::Var var){
	return myUseTable.isLineUses(line, var);
}

bool PKB::isProcUses(Type::Index::Proc proc, Type::Index::Var var){
	return myUseTable.isProcUses(proc, var);
}

/****************************Affects****************************************/

bool PKB::setLastModified(Type::Map::LineMatrix& lineMatrix){
	return myModifyTable.setLastModified(lineMatrix);
}

bool PKB::setNextModified(Type::Map::LineMatrix& lineMatrix){
	return myModifyTable.setNextModified(lineMatrix);
}

bool PKB::setCommon(Type::Entity::Line entity, Type::Map::ParentMatrix& parentMatrix){
	commonParentSetFlag = true;
	return myCommonParent.setCommon(entity, parentMatrix);
}

Type::Index::Line PKB::getCommon(Type::Entity::Line entity, Type::Index::Line parentOne, 
	Type::Index::Line parentTwo){
		return myCommonParent.getCommon(entity, parentOne, parentTwo);
}

bool PKB::isAffects(Type::Index::Line firstLine, Type::Index::Line secondLine){
	// check if the given first and second lines are valid, and both must be assignment statement
	if(!isLineExists(firstLine) || !isLineExists(secondLine)
		|| !isLineEntity(firstLine, Type::Entity::ASSIGNMENT_LINE_ENTITY)
		|| !isLineEntity(secondLine, Type::Entity::ASSIGNMENT_LINE_ENTITY)){
			return false;
	}

	// get the modified variable at the first line
	Type::List::Var modifiedVars = getModifiedVarsByLine(firstLine);
	Type::Index::Var modifiedVar = modifiedVars.front();

	// if second line uses the modified variable and
	// isNext* relationship is true for first and second line
	if(isLineUses(secondLine, modifiedVar) && isNextStar(firstLine, secondLine)){
		Type::Index::Line lastModified = myModifyTable.getLastModified(secondLine, modifiedVar);
		Type::Index::Line nextModified = myModifyTable.getNextModified(firstLine, modifiedVar);
		Type::Index::Line commonWhile;
		Type::Index::Line endOfWhile;
		Type::Index::Line firstParent = getParent(firstLine);
		Type::Index::Line secondParent = getParent(secondLine);

		//std::cout<<"AFFECT "<<firstLine<<" "<<secondLine<<"\n";		
		//std::cout<<"2nd line "<<secondLine<<" uses var "<<getVarName(modifiedVar);
		//std::cout<<" "<<isLineUses(secondLine, modifiedVar)<<"\n";
		//std::cout<<"nextStar of ("<<firstLine<<","<<secondLine<<") "<<isNextStar(firstLine,secondLine)<<"\n";

		// either first or second line is at top most level; 
		if(firstParent == -1 || secondParent == -1){
			commonWhile = -1;
		}else{
			commonWhile = getCommon(Type::Entity::WHILE_LINE_ENTITY, firstParent, secondParent);
		}

		bool hasCommonWhile = commonWhile > 0;
		// there is a common while parent that containes first and second line
		if(hasCommonWhile){
			endOfWhile = getLastOfWhile(commonWhile);
		}else{
			// if there is no common while parent
			endOfWhile = commonWhile;
		}

		//std::cout<<"first parent "<<firstParent<<" second parent "<<secondParent<<"\n";
		//std::cout<<"last modified of "<<getVarName(modifiedVar)<<"("<<modifiedVar<<") is "<<lastModified;
		//std::cout<<" before line "<<secondLine<<"\n";
		//std::cout<<"next modified of "<<getVarName(modifiedVar)<<"("<<modifiedVar<<") is "<<nextModified;
		//std::cout<<" after line "<<firstLine<<"\n";
		//std::cout<<"common while of "<<firstParent<<","<<secondParent<<" is "<<commonWhile<<"\n";
		//std::cout<<"end of while "<<commonWhile<<" is "<<endOfWhile<<"\n";

		bool isNextBiggerEndWhile;
		bool isNextBiggerEqualSecond;

		// no more lines that will modify the variable
		if(nextModified==0){
			isNextBiggerEndWhile = true;
			isNextBiggerEqualSecond = true;
		} else {
			if (isLineEntity(nextModified, Type::Entity::IF_LINE_ENTITY)) {
				// nextModified line is an if, so it is possible that secondLine is within it.
				// Need to check if the secondLine is within this IF
				int lastLineOfElse = getLastOfIf(nextModified).at(1);
				// Check if secondLine is within it
				if (secondLine <= lastLineOfElse) {
					isNextBiggerEqualSecond = true;
				} else {
					isNextBiggerEqualSecond = nextModified >= secondLine;
				}
			} else {
				isNextBiggerEqualSecond = nextModified >= secondLine;
			}
			isNextBiggerEndWhile = nextModified > endOfWhile;
		}

		bool isLastSmallerEqualFirst = lastModified <= firstLine;
		bool isLastSmallerStartWhile;

		// there is no common while parent, any last modified line index would be valid
		if( !hasCommonWhile){
			isLastSmallerStartWhile = true;
		}else{
			isLastSmallerStartWhile = lastModified < commonWhile;
		}

		// find common if of first and second
		Type::Index::Line commonIf;
		commonIf = getCommon(Type::Entity::IF_LINE_ENTITY, firstParent, secondParent);
		bool hasCommonIf = commonIf > 0;

		// check if first and second are in the same if or else statement list
		Type::List::Line thenElseOfIf;
		bool isSameStatementList = false;
		if(hasCommonIf){
			// get starting line of then and else parts of the common if
			thenElseOfIf = getSuccessorNext(commonIf);
			assert(thenElseOfIf.size() == 2);
			Type::Index::Line child1 = thenElseOfIf[0];
			Type::Index::Line child2 = thenElseOfIf[1];

			Type::Index::Line startOfThen;
			Type::Index::Line endOfThen;
			// the child with bigger value is the starting line of else part
			if(child1 > child2){
				startOfThen = child2;
				endOfThen = child1 - 1;
			}else{
				startOfThen = child1;
				endOfThen = child2 - 1;
			}

			bool isFirstInThen = firstLine >= startOfThen && firstLine <= endOfThen;
			bool isSecondInThen = secondLine >= startOfThen && secondLine <= endOfThen;

			isSameStatementList = !(isFirstInThen ^ isSecondInThen);
		}

		//std::cout<<"common if of "<<firstLine<<","<<secondLine<<" is "<<commonIf<<"\n";
		//std::cout<<"line "<<firstLine<<" and line "<<secondLine<<" is in same statement list "<<isSameStatementList<<"\n";

		bool affectResult;
		// when first line is smaller than second line
		// first and second lines are in the same statement list or isFollows*(firstLine, secondLine) is TRUE
		if(firstLine < secondLine && ( !hasCommonIf || isSameStatementList || isFollowStar(firstLine, secondLine))){
			// normal checking:
			// check if the next modified line is bigger or equal to second line 
			// and if the last modified line is smaller or equal to first line
			affectResult = isNextBiggerEqualSecond && isLastSmallerEqualFirst;
			//std::cout<<"AFFECT "<<firstLine<<" "<<secondLine<<" "<<affectResult<<"\n";		
			return affectResult;
		}else{
			// special checking:
			// check if the next modified line is bigger than end of while
			// and if the last modified line is smaller than start of while
			affectResult = isNextBiggerEndWhile && isLastSmallerStartWhile;
			//std::cout<<"AFFECT "<<firstLine<<" "<<secondLine<<" "<<affectResult<<"\n";
			return affectResult;
		}
	}
	//std::cout<<"AFFECT "<<firstLine<<" "<<secondLine<<" 0\n";		
	return false;
}

Type::List::Line& PKB::getAffectsStar(Type::Index::Line line){
	return getAffects(false, true, line);
}

Type::List::Line& PKB::getAffectedStar(Type::Index::Line line){
	return getAffects(true, true, line);
}

Type::List::Line& PKB::getAffects(Type::Index::Line line){
	return getAffects(false, false, line);
}

Type::List::Line& PKB::getAffected(Type::Index::Line line){
	return getAffects(true, false, line);
}

bool PKB::isAffectsStar(Type::Index::Line firstLine, Type::Index::Line secondLine){
	if(!isLineExists(firstLine) || !isLineExists(secondLine)){
		return false;
	}

	Type::List::Line assigns = getPossibleAffectLinesFrom(true, firstLine);
	Type::Set::Line assignsToCheck = Type::Set::Line(assigns.begin(), assigns.end());
	Type::List::Line result;
	bool affectResult = recurAffects(false, false, true, firstLine, secondLine, assignsToCheck, result); 
	return affectResult;
}

Type::List::Line& PKB::getAffects(bool isFirst, bool isStar, Type::Index::Line line){
	Type::List::Line* resultList = new Type::List::Line();

	if(!isLineExists(line) 
		|| !isLineEntity(line, Type::Entity::ASSIGNMENT_LINE_ENTITY)){
			return *resultList;
	}

	Type::List::Line assigns = getPossibleAffectLinesFrom(isFirst, line);
	Type::Set::Line assignsToCheck = Type::Set::Line(assigns.begin(), assigns.end());

	Type::Index::Line first = -1;
	Type::Index::Line second = -1;

	if(isFirst){
		first = line;
	}else{
		second = line;
	}

	recurAffects(true, isFirst, isStar, first, second, assignsToCheck, *resultList);
	return *resultList;
}

const Type::List::Line& PKB::getPossibleAffectLinesFrom(bool isFirst, Type::Index::Line line){
	Type::List::Line* lines = new Type::List::Line();
		
	if(!isLineExists(line)){
		return *lines;
	}

	// get the start and end of the procedure
	Type::Index::Proc tmpProc = getProcIndexOfLine(line);
	Type::Pair::StartEnd startEnd = getProcStartEnd(tmpProc);
	Type::Index::Line start = startEnd.first;
	Type::Index::Line end = startEnd.second;
	Type::List::Line assigns = getLinesByEntity(Type::Entity::ASSIGNMENT_LINE_ENTITY);
	Type::Index::Line tmpLine;
	bool nextStar;

	for(unsigned int h=0; h<assigns.size(); h++){
		tmpLine = assigns.at(h);
		
		if(isFirst){
			nextStar = isNextStar(line, tmpLine);
		}else{
			nextStar = isNextStar(tmpLine, line);
		}

		if(tmpLine >= start && tmpLine <= end && nextStar){
			lines->push_back(tmpLine);
		}
	}

	return *lines;
}

bool PKB::recurAffects(bool isGet, bool isFirst, bool isStar, Type::Index::Line first, Type::Index::Line second, 
	Type::Set::Line& assigns, Type::List::Line& results){
		// this function cannot solve isAffects()
		assert( isGet || isStar);

		Type::Index::Line tmpLine, recurLine, lineGiven;
		Type::List::Line recurList;
		bool affect;

		Type::Set::Line::iterator it = assigns.begin();
		while (it != assigns.end()){
			tmpLine = *it;

			// check for getAffect( first, _ ) or isAffects( first, _ )
			if(isFirst || !isGet){
				affect = isAffects(first, tmpLine);
				lineGiven = first;
			} else {
				affect = isAffects(tmpLine, second);
				lineGiven = second;
			}

			if(affect){
				// record the lines for Affects
				results.push_back(tmpLine);

				// record the lines to recur for Affects*
				if(isStar){
					recurList.push_back(tmpLine);
				}

				// since there tmpline already checked for isAffects relationship
				// and isAffects = TRUE, so it should be included in the next search
				it = assigns.erase(it);
			}else{
				it++;
			}
		}

		bool result = false;
		// when there is at least one line to recur
		for(unsigned int h=0; h<recurList.size() && isStar && !result;h++){
			recurLine = recurList.at(h);

			if(isGet){
				if(isFirst && lineGiven != recurLine){
					// getAffects*( recurLine , _ )
					recurAffects(isGet, isFirst, isStar, recurLine, second, assigns, results);
				}else{
					// getAffects*( _ , recurLine )
					recurAffects(isGet, isFirst, isStar, first, recurLine, assigns, results);
				}
			}else{
				// isAffects*( recurLine , second )
				if(recurLine == second){
					// isAffects*( recurLine , second ) is found
					result = true;
				}else if (lineGiven != recurLine){
					// recur on checking isAffects*( recurLine , second);
					result = recurAffects(isGet, isFirst, isStar, recurLine, second, assigns, results);
				}

				// stop recurring assignment lines when an isAffects* is found
				if(result){
					break;
				}
			}
		}

		if(isGet){
			// getAffects( _ , second) or getAffects( first, _ ) 
			// or getAffects*( _ , second ) or getAffects*( first , _ )
			// will always reach here
			return true;
		}else{
			// isAffects( first, second) or isAffects*(first, second)
			// will always reach here
			return result;
		}
}

/****************AffectBip**************/
/// return the list of lines that affectBip directly the given line (all x such that affectsBIP(x,givenLine))
Type::List::Line& PKB::getAffectBip(Type::Index::Line line){
	Type::List::Line *results = new Type::List::Line();
	if ( !isLineExists(line)) {
		return *results;
	}
	if ( !isLineEntity(line, Type::Entity::ASSIGNMENT_LINE_ENTITY)) {
		return *results;
	}
	
	// Here, we are ensured that the line is valid and is an ASSIGN

	// Similar to getAffectedBip, but we have to traverse predecessors,
	// and check if they modify any of the used variables.
	std::unordered_map<Type::Index::Line, bool> traversedMap;
	std::unordered_map<Type::Index::Var, bool> usedVarsMap; 
	Type::List::Var varsUsed = getUsedVarsByLine(line);
	if (varsUsed.empty()) {
		return *results;
	}
	for (auto varUsed = varsUsed.begin(); varUsed != varsUsed.end(); varUsed++) {
		usedVarsMap.insert( std::make_pair(*varUsed, true) );
	}
	
	std::unordered_map<Type::Index::Line, bool> nextBipStarMap; // to ensure that we do not use nextBip edges wrongly
	Type::List::Line nextBipStarList = getPredecessorNextBipStar(line);
	for (auto n = nextBipStarList.begin(); n != nextBipStarList.end(); n++) {
		nextBipStarMap.insert( std::make_pair(*n, true) );
	}

	getAffectBip_Recursive(line, usedVarsMap, &traversedMap, nextBipStarMap, results);

	return *results;
}
/// return the list of directly affectedBip lines by the given line (all y such that affectsBIP(givenLine,y))
Type::List::Line& PKB::getAffectedBip(Type::Index::Line line){
	Type::List::Line *results = new Type::List::Line();
	if ( !isLineExists(line)) {
		return *results;
	}
	if ( !isLineEntity(line, Type::Entity::ASSIGNMENT_LINE_ENTITY)) {
		return *results;
	}

	// Here, we are ensured that the line is valid and is an ASSIGN

	Type::List::Line assignList = getLinesByEntity(Type::Entity::ASSIGNMENT_LINE_ENTITY);
	for (auto assignIt = assignList.begin(); assignIt != assignList.end(); assignIt++) {
		if (isAffectBip(line, *assignIt)) {
			results->push_back(*assignIt);
		}
	}
	return *results;
	/* 
	 * The following is commented out because it does not traverse the nextBIP graph
	 * properly. When a procedure is called and it reaches the exit point, the nextBIP nodes
	 * added is currently ALL the exitToIndexes, where it should be only the line after the
	 * line which called this procedure.
	 * If labelling of edges is done, it will be possible to do. However,
	 * since checking isAffectsBip each time is O(c) time where c is the number of call statements,
	 * it should not be too much of a time complexity difference, assuming that there are not that
	 * many call statements in a program.
	 */
	//}
	//// First, get all the exit points of all procs and insert it into the exitPointsMap
	//// that will be checked against 
	//std::unordered_map<Type::Index::Line, bool> exitPointsMap;
	//const Type::List::Proc& procList = getProcIndices();
	//for (auto procIt = procList.begin(); procIt != procList.end(); procIt++) {
	//	Type::List::Line exitPoints = getProcExitPoints(*procIt);
	//	for (auto exitPoint = exitPoints.begin(); exitPoint != exitPoints.end(); exitPoint++) {
	//		exitPointsMap.insert( std::make_pair(*exitPoint, true) );
	//	}
	//}

	//Type::Index::Var varModified = getModifiedVarsByLine(line).at(0);
	//if (line == 101)
	//	cout << "varModified = " << varModified << endl;
	//// Traverse the CFGBip (nextBIP)
	//std::unordered_map<Type::Index::Line, bool> traversedMap; // so that we do not traverse an already traversed node

	//std::unordered_map<Type::Index::Line, bool> nextBipStarMap; // to ensure that we do not use nextBip edges wrongly
	//Type::List::Line nextBipStarList = getSuccessorNextBipStar(line);
	//for (auto n = nextBipStarList.begin(); n != nextBipStarList.end(); n++) {
	//	nextBipStarMap.insert( std::make_pair(*n, true) );
	//}

	//Type::List::Line nextBipNodes; // Use these nodes to traverse
	//nextBipNodes.push_back(line);
	//for (unsigned int i = 0; i < nextBipNodes.size(); i++) {
	//	Type::Index::Line currentLine = nextBipNodes.at(i);
	//	if (line == 101)
	//		cout << "checking currentLine = " << currentLine << endl;
	//	Type::List::Line newNextBipNodes = getSuccessorNextBip(currentLine);
	//	for (auto newNextBip = newNextBipNodes.begin(); newNextBip != newNextBipNodes.end(); newNextBip++) {
	//		if ( !Utilities::isKeyInMap_TypeType(traversedMap, *newNextBip)
	//			&& Utilities::isKeyInMap_TypeType(nextBipStarMap, *newNextBip)) {
	//			// Unique newNextBip that is a good nextBip
	//				
	//			if (line == 101)
	//				cout << "checking nextBip line = " << *newNextBip << endl;
	//			// If the nextBip is an ASSIGN and uses the modified var,
	//			// we add it to the results.
	//			if (isLineEntity(*newNextBip, Type::Entity::ASSIGNMENT_LINE_ENTITY)
	//				&& isLineUses(*newNextBip, varModified)) {
	//					results->push_back(*newNextBip);
	//			}
	//			// We also want to traverse this newNextBip if it is NOT an ASSIGN/CALL that modifies the var
	//			if ( !(isLineEntity(*newNextBip, Type::Entity::ASSIGNMENT_LINE_ENTITY)
	//					&& isLineModifies(*newNextBip, varModified)) ) {
	//				nextBipNodes.push_back(*newNextBip);
	//			}

	//			traversedMap.insert( std::make_pair(*newNextBip, true) );
	//		}
	//	}
	//}
	//return *results;
}
/// check if the given line 1 directly affectBip the given line 2 
bool PKB::isAffectBip(Type::Index::Line line1, Type::Index::Line line2){
	if ( !isLineExists(line1) || !isLineExists(line2)) {
		return false;
	}
	return isAffectBip_Yude(line1, line2);
}

// Recursive helper function for getAffectBip
void PKB::getAffectBip_Recursive(const Type::Index::Line line, const std::unordered_map<Type::Index::Var, bool>& usedVarsMap, 
	std::unordered_map<Type::Index::Line, bool>* traversedMap, const std::unordered_map<Type::Index::Line, bool>& predecessorBipStarMap,
	Type::List::Line* results) {
		if (usedVarsMap.empty()) {
			// No vars used, so return
			return;
		}
		// Idea:
		//	For the given line, check its predecessors to see if they are ASSIGN lines that 
		//	modify any var in the usedVarsMap. Add them to the results if they do, and add the modified var to
		//	a varsToBeDeletedList so as to delete them from the usedVarsMap to be used in the next recursion.
		//	As for the recursion, use the predecessor as the line argument.
		Type::List::Line predecessors = getPredecessorNextBip(line);
		for (auto preD = predecessors.begin(); preD != predecessors.end(); preD++) {
			if ( !Utilities::isKeyInMap_TypeType(*traversedMap, *preD)
				&& Utilities::isKeyInMap_TypeType(predecessorBipStarMap, *preD)) {
				// Unique predecessor and is a good predecessorNextBip

				Type::Index::Var modifiedVar = getModifiedVarsByLine(*preD).at(0);
				if (isLineEntity(*preD, Type::Entity::ASSIGNMENT_LINE_ENTITY)
					&& Utilities::isKeyInMap_TypeType(usedVarsMap, modifiedVar)) {
						// If predecessor is ASSIGN that modify a variable in the usedVarsMap,
						// add to results and create a new usedVarsMap2 which is a copy of the usedVarsMap
						// but without this var.
						results->push_back(*preD);

						std::unordered_map<Type::Index::Line, bool> usedVarsMap2(usedVarsMap);
						usedVarsMap2.erase(modifiedVar);

						traversedMap->insert( std::make_pair(*preD, true) );
						getAffectBip_Recursive(*preD, usedVarsMap2, traversedMap, predecessorBipStarMap, results);
				} else {
					// Otherwise, the predecessor is either not an ASSIGN,
					// or is an ASSIGN that doesn't modify any of the used vars.
					// Either way, we recurse on it with the same usedVarsMap
					traversedMap->insert( std::make_pair(*preD, true) );
					getAffectBip_Recursive(*preD, usedVarsMap, traversedMap, predecessorBipStarMap, results);
				}
			}
		}
}

bool PKB::isAffectBip_Yude(Type::Index::Line x, Type::Index::Line y) {
	/**-------------------------------------------------------------------
	 *	Algorithm:
	 *
	 *	Base checks:
	 *		- x and y are valid and ASSIGN type
	 *		- variable v modified by x is used by y
	 *		- nextBIP*(x,y)
	 *
	 *	Case 1: x and y in same procedure
	 *		Case 1a: x >= y (definitely need to loop back to get to y)
	 *			- hasLoopBackRoute(x,y,v)
	 *
	 *		Case 1b: x and y have a common if and are in different then/else
	 *			- hasLoopBackRoute(x,y,v)
	 *
	 *		Case 1c: Anything else (x < y and have no common if or have a common if but are in the same then/else
	 *			- hasDirectRouteInProc(x,y,v)
	 *
	 *	Case 2: x and y in different procedures
	 *		- hasOutRoute(x,y,v)
	 *-------------------------------------------------------------------*/
	/* BASE CHECKS */
	// Check if lines x and y are ASSIGN type
	if ( !isLineEntity(x, Type::Entity::ASSIGNMENT_LINE_ENTITY) || !isLineEntity(y, Type::Entity::ASSIGNMENT_LINE_ENTITY)) {
		return false;
	}
	// Check if line y uses the variable v that is modified by x
	Type::Index::Var v = getModifiedVarsByLine(x).at(0); // x is an ASSIGN line so it must have ONE modified var
	if ( !isLineUses(y, v)) {
		return false;
	}
	// Check if nextBIP*(x,y)
	if ( !isNextBipStar(x, y)) {
		return false;
	}

	// Here, we are ensured that x and y are ASSIGN type lines,
	// y uses the variable v modified by x,
	// and nextBIP*(x,y) is true.

	bool hasThroughRoute = false;
	// Case 1: x and y in same procedure
	// Case 2: x and y in different procedures
	Type::Index::Proc xProc = getProcIndexOfLine(x);
	Type::Index::Proc yProc = getProcIndexOfLine(y);
	if (xProc == yProc) {
		// Case 1
		// Case 1a: x >= y (definitely need to loop back to get to y)
		// Case 1b: x and y have a common if and are in different then/else
		// Case 1c: Anything else (x < y and have no common if or have a common if but are in the same then/else
		
		// Need to find common if for case 1b
		bool hasCommonIf;
		bool xInThen;
		bool yInThen;

		findCommonIf(x, y, &hasCommonIf, &xInThen, &yInThen);

		if (x >= y) {
			// Case 1a: x >= y (definitely need to loop back to get to y)
			hasThroughRoute = hasLoopBackRoute(x, y, v);
		} else if (hasCommonIf && (xInThen ^ yInThen)) {
			// Case 1b: x and y have a common if and are in different then/else
			hasThroughRoute = hasLoopBackRoute(x, y, v);
		} else {
			// Case 1c: Anything else (x < y and have no common if or have a common if but are in the same then/else
			hasThroughRoute = hasDirectRouteInProc(x, y, v);
		}
	} else {
		// Case 2
		hasThroughRoute = hasOutRoute(x, y, v);
	}

	return hasThroughRoute;
}

// Checks if there is a direct route straight down from x to y.
// Definition: x has a direct route in its proc to y which does not modify v iff
//	1. x and y are in the same proc
//	2. x < y AND has no common if, OR x < y AND has a common if BUT are in the same then/else
//	3. there exists some control path that only contains lines in {x, ... ,y} such that v is not modified 
//  by any ASSIGN or CALL (for sure) along this path (except for y, and x if it is not a CALL)
bool PKB::hasDirectRouteInProc(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v) {
	// Ensure valid lines
	if ( !isLineExists(x) || !isLineExists(y)) {
		return false;
	}
	// Ensure x and y are in same proc
	Type::Index::Proc xProc = getProcIndexOfLine(x);
	Type::Index::Proc yProc = getProcIndexOfLine(y);
	if (xProc != yProc) {
		return false;
	}
	// Ensure x < y
	if (x >= y) {
		return false;
	}
	// Ensure x is not a CALL that is a wall
	if (isLineEntity(x, Type::Entity::CALL_LINE_ENTITY) && isLineAWall(x, v)) {
		return false;
	}

	// Check for common if
	bool hasCommonIf;
	bool xInThen;
	bool yInThen;

	Type::Index::Line commonIf = findCommonIf(x, y, &hasCommonIf, &xInThen, &yInThen);
	// Ensure that, even if x and y have a common if, they are in the same then/else
	if (hasCommonIf) {
		bool inSameThenOrElse = !(xInThen ^ yInThen);
		if ( !inSameThenOrElse) {
			return false;
		}
	}

	/**	1. x and y are in the same proc
	 *	2. x < y AND has no common if, OR x < y AND has a common if BUT are in the same then/else
	 *	3. there exists some control path that only contains lines in {x, ... ,y} such that v is not modified 
	 *		(branch in procedure allowed) along this path (except except for x and y themselves)
	 */
	// Here, we have already ensured conditions 1 and 2.
	// Time to check if condition 3 is true!
	Type::Index::Line nextModFromX = myModifyTable.getNextModified(x, v);
	Type::Index::Line lastModFromY = myModifyTable.getLastModified(y, v);
	// If the next time modified from X (nm) is after OR equal to Y OR nm <= 0
	// AND last time modified from Y (lm) is before OR equal to X OR lm <= 0,
	// then we we have found a route!
	// Otherwise, we need to try and push nm to >= Y (if nm is not a wall OR if it is an IF wall then it may be pushed)
	// and push lm to <= x (if lm is not a wall OR if it is an IF wall then it may be pushed)
	while (nextModFromX > 0 && nextModFromX < y) {
		if ( !isLineAWall(nextModFromX, v)) {
			nextModFromX = myModifyTable.getNextModified(nextModFromX, v);
		} else if (isLineEntity(nextModFromX, Type::Entity::IF_LINE_ENTITY)) {
			// Is an IF wall, it can still be pushed if y is in it
			Type::List::Line lastOfIf = getLastOfIf(nextModFromX);
			if (y > lastOfIf.at(1)) {
				// y is not in it, cannot be pushed, this is a true wall
				return false;
			} else {
				// y is in it
				// y in then -> go to first stmt of then
				// y in else -> go to first stmt of else
				if (y <= lastOfIf.at(0)) {
					// y in then
					nextModFromX++; // Might not be really the next mod (and can be a WHILE)
				} else {
					// y in else
					nextModFromX = lastOfIf.at(0) + 1; // Might not really be the next mod (and can be a WHILE)
				}
			}
		} else {
			// is a non-IF wall (CALL or ASSIGN, because WHILE can't be walls), so definitely can't cross
			return false;
		}
	}

	if (nextModFromX > 0 && nextModFromX < y) {
		// there is definitely a true wall between x and y
		return false;
	}

	// Here, nextModFromX > y or nextModFromX <= 0

	while (lastModFromY > x) {
		if ( !isLineAWall(lastModFromY, v)) {
			lastModFromY = myModifyTable.getLastModified(lastModFromY, v);
		} else if (isLineEntity(lastModFromY, Type::Entity::IF_LINE_ENTITY)) {
			// Is an IF wall, it can still be pushed if x is in it
			// (in this case because of the loop condition x < lastModFromY so x must be in it)
			Type::List::Line lastOfIf = getLastOfIf(lastModFromY);
			// x in then -> go to last stmt of then
			// x in else -> go to last stmt of else
			if (x <= lastOfIf.at(0)) {
				// x in then
				lastModFromY = lastOfIf.at(0); // Might not be really the next mod (cannot be WHILE)
			} else {
				// x in else
				lastModFromY = lastOfIf.at(1); // Might not really be the next mod (cannot be WHILE)
			}
		} else {
			// is a non-IF wall, so definitely can't cross
			return false;
		}
	}

	// At this point, lastModFromY <= x
	// If lastModFromY == x AND x is an IF, then there is no way to get to it 
	// without modifying v along the way (modified within x itself)
	// Otherwise we have a route!
	if (lastModFromY == x && isLineEntity(x, Type::Entity::IF_LINE_ENTITY)) {
		return false;
	} else {
		return true;
	}
}

// Checks if there is a direct route straight down from x to y. (includeX/includeY set-able)
// VERY similar to hasDirectRouteInProc except that x == y is acceptable and considered 'reached' 
// as long as includeX or includeY is false.
bool PKB::isReachable(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v, bool includeX, bool includeY) {
	if (x == y && (!includeX || !includeY)) {
		// already reached
		return true;
	}
	if (includeX) {
		// Check x if it is a true wall to reaching y (CALL/ASSIGN)
		if ( (isLineEntity(x, Type::Entity::CALL_LINE_ENTITY) || isLineEntity(x, Type::Entity::ASSIGNMENT_LINE_ENTITY))
			&& isLineAWall(x, v)) {
				return false;
		}
	}

	if (includeY) {
		// Check y if it is a true wall itself (CALL/ASSIGN)
		if ( (isLineEntity(y, Type::Entity::CALL_LINE_ENTITY) || isLineEntity(y, Type::Entity::ASSIGNMENT_LINE_ENTITY))
			&& isLineAWall(y, v)) {
				return false;
		}
	}
	
	// Here, we know that the x and y lines are not walls to v,
	// or even if they are they are not included
	if (x == y) {
		// reached
		return true;
	} else {
		return hasDirectRouteInProc(x, y, v);
	}
}

// Checks if there is a path such that we can exit the proc x is in, starting from x, without modifying v.
// includeX/includeExitPoint is set-able.
bool PKB::checkCanExitProc(Type::Index::Line x, Type::Index::Var v, bool includeX, bool includeExitPoint) {
	Type::Index::Proc xProc = getProcIndexOfLine(x);
	Type::List::Line exitPoints = getProcExitPoints(xProc);
	
	if (includeX && includeExitPoint) {
		if ( (isLineEntity(x, Type::Entity::ASSIGNMENT_LINE_ENTITY) || isLineEntity(x, Type::Entity::CALL_LINE_ENTITY))
			&& isLineAWall(x, v)) {
				return false;
		}
	}

	// Check if we can immediately exit from x
	for (auto exitPoint = exitPoints.begin(); exitPoint != exitPoints.end(); exitPoint++) {
		if (isReachable(x, *exitPoint, v, includeX, includeExitPoint)) {
			return true;
		}
	}

	// Here, we were unable to reach the exit points directly,
	// but it may be the case that we have while loops to help us get there,
	// so keep traversing while loops one at a time and checking if
	// we can reach any exitPoints
	bool hasWhile;
	Type::Index::Line whileLine = findCommonWhile(x, x, &hasWhile);
	if ( !hasWhile) {
		// No while loop, so we can stop already
		return false;
	}
	Type::Index::Line currentLine = x;
	while (hasWhile) {
		// Ensure currentLine can reach the end of the loop
		// To do so, keep checking the nextModified until we are out of the loop.
		Type::Index::Line endOfWhile = getLastOfWhile(whileLine);
		while (currentLine > 0 && currentLine <= endOfWhile) {
			if (currentLine != x && isLineAWall(currentLine, v)) {
				return false;
			}
			currentLine = myModifyTable.getNextModified(currentLine, v);
		}
		// Got out of the while loop, so traverse to the next while loop
		currentLine = whileLine;
		whileLine = findCommonWhile(whileLine, whileLine, &hasWhile);
	}
	// If we are here, it means that we managed to traverse to the highest level while loop
	// currentLine will hold the highest level while loop
	// Just check if it can reach any exit points
	for (auto exitPoint = exitPoints.begin(); exitPoint != exitPoints.end(); exitPoint++) {
		if (isReachable(currentLine, *exitPoint, v, includeX, includeExitPoint)) {
			return true;
		}
	}

	return false;
}

// Checks if there is a loop back route from x to y that may use a while loop to loop back
// or may exit the proc through its exit points and possibly come back through a call stmt
// calling the proc which x is in.
// Definition: x has a loop back route to y which does not modify v iff
//	hasDirectRouteInProc(x,y,v) OR...
//	1. x and y are in the same proc
//	2. x < y AND has common if AND are in different stmtlsts of the common if,
//		OR x >= y
//	3. there exists some control path by either a while loop or by exiting the proc X,
//		and finally coming back to proc X again through a call stmt somewhere.
bool PKB::hasLoopBackRoute(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v) {
	if (hasDirectRouteInProc(x, y, v)) {
		// Immediately the direct route is a 'loop back route'
		return true;
	}

	// Here, we know that hasDirectRouteInProc(x, y, v) is false.
	// This implies one or more of the following:
	// 1. x and y are in different procs
	// 2. x >= y
	// 3. x < y AND has common if AND are in different stmtlsts of the common if
	// 4. if none of the above, then there is simply no way to loop back since even
	//		a direct route failed while it was possible to get a direct control path.

	// Ensure x and y are in same procs
	Type::Index::Proc xProc = getProcIndexOfLine(x);
	Type::Index::Proc yProc = getProcIndexOfLine(y);
	if (xProc != yProc) {
		return false;
	}

	// Ensure that either x >= y or x < y but has a common if and are in different stmtlsts
	// Check for common if
	bool hasCommonIf;
	bool xInThen;
	bool yInThen;

	Type::Index::Line commonIf = findCommonIf(x, y, &hasCommonIf, &xInThen, &yInThen);
	
	// Ensure that either x >= y OR x < y but has a common if and are in different stmtlsts
	if (x < y) {
		if (hasCommonIf) {
			// has common if
			bool inSameThenOrElse = !(xInThen ^ yInThen);
			if (inSameThenOrElse) {
				// has common if but not in different stmtlsts
				return false;
			}
		} else {
			// no common if but x < y (since no direct route)
			return false;
		}
	}

	// Here, we are ensured that there is no direct downward path from x to y even though they are in the same procedure.
	// Either x >= y or x < y but has common if and are in different stmtlsts
	// Time to check for loop back route!

	// First, we check for a common while loop to help loop back.
	bool hasCommonWhile;
	Type::Index::Line commonWhile;
	if (x == y && isLineEntity(x, Type::Entity::WHILE_LINE_ENTITY)) {
		commonWhile = x;
		hasCommonWhile = true;
	} else {
		commonWhile = findCommonWhile(x, y, &hasCommonWhile);
	}

	// Observation: if the common while loop cannot help with the loop back route,
	//		then even exiting the procedure and coming back will not help
	//		because it means that there is a blockage within the loop itself
	//		(either from the start of the loop to y, or from x to the end of the loop.
	//		If the blockage is from the start of the loop to y, starting from the start of the proc
	//		will not help. If the blockage is from x to the end of the loop, there is no way to even exit the proc
	//		without being blocked.)
	if (hasCommonWhile) {
		// Ensure there is a direct route from start of loop to y
		if (commonWhile != y && !hasDirectRouteInProc(commonWhile, y, v)) {
			return false;
		}
		// Now, left to check if its possible to get out of the while loop without a blockage
		Type::Index::Line currentLine = x;
		Type::Index::Line endOfWhile = getLastOfWhile(commonWhile);
		while (currentLine > 0 && currentLine <= endOfWhile) {
			if (currentLine != x && isLineAWall(currentLine, v)) {
				return false;
			}
			currentLine = myModifyTable.getNextModified(currentLine, v);
		}
		// Here, we definitely made it past the end of the loop without reaching a wall!
		return true;
	}

	// Here, there is no common while.
	// This implies that the only possible way left is by exiting this proc and trying to come back through call stmts
	// from other places!
	// Ensure that there is a route from the start of the proc to y,
	// because otherwise there is no point even trying to go out of the proc to only come back into a wall.
	Type::Index::Line xProcStart = getProcStartEnd(xProc).first;
	if ( !isReachable(xProcStart, y, v, true, false)) {
		return false;
	}

	// Now we are ensured that there is a control path from the proc start to y that does not modify v.
	// We just need to exit this proc (possibly to multiple places) and check if
	// we are able to come back through call stmts without being blocked.

	// First, ensure that we can exit the proc from x (can reach some exit point)
	Type::List::Line exitPoints = getProcExitPoints(xProc);
	bool canExitProc = checkCanExitProc(x, v, false, true);
	if ( !canExitProc) {
		return false;
	}

	Type::List::Line procExitToIndexes = getProcExitToIndexes(xProc);
	Type::List::Line calledToIndexes;
	const Type::List::Line& callList = getLinesByEntity(Type::Entity::CALL_LINE_ENTITY);
	std::map<Type::Index::Line, bool> exitToIndexesMap;
	for (unsigned int i = 0; i < procExitToIndexes.size(); i++) {
		Type::Index::Line currentLine = procExitToIndexes.at(i);
		Type::Index::Proc currentLineProc = getProcIndexOfLine(currentLine);
		// Find out if the currentLine is able to get to any of the call stmts.
		// For the call stmts it can get to, add the starting index of the called proc to the procExitToIndexes
		// so that those will be checked too. (Of course, add uniquely to avoid redundant work)
		for (unsigned int j = 0; j < callList.size(); j++) {
			Type::Index::Line callLine = callList.at(j);
			Type::Index::Proc calledProc = getCalledByLine(callLine);
			bool isTheCallWeNeed = calledProc == xProc;
			bool isReachable;
			Type::Index::Proc callLineProc = getProcIndexOfLine(callLine);
			if (callLineProc != currentLineProc) {
				// Not in same proc, definitely not reachable
				isReachable = false;
			} else if (currentLine == callLine) {
				// In same proc
				// If we are already on the call line, we are on it so it is reachable.
				isReachable = true;
			} else {
				// In same proc but not on the call line.
				if (isLineAWall(currentLine, v)) {
					// Here we are not on the call line, and the currentLine is a wall.
					// However, if currentLine is a IF line,
					// we may still be able to reach the call line.
					if ( (isLineEntity(currentLine, Type::Entity::IF_LINE_ENTITY)) 
						&& hasLoopBackRoute(currentLine, callLine, v)) {
							isReachable = true;
					} else {
						// CALL or ASSIGN wall, which are true walls
						isReachable = false;
					}
				} else {
					// Here we are not on the call line, and the currentLine is NOT a wall
					isReachable = hasLoopBackRoute(currentLine, callLine, v);
				}
			}
			// isReachable has been set
			// If it is reachable, then check if it is the call line we need
			if (isReachable) {
				if (isTheCallWeNeed) {
					return true;
				} else {
					// Is reachable but not the call we need,
					// so add the start index of the proc this callLine calls to the calledToIndexes if it hasn't been added before
					Type::Index::Line startOfCalledProc = getProcStartEnd(calledProc).first;
					if ( !Utilities::isKeyInMap_TypeType(exitToIndexesMap, startOfCalledProc)) {
						calledToIndexes.push_back(startOfCalledProc);
						exitToIndexesMap.insert( std::make_pair(startOfCalledProc, true) );
					}
				}
			} 
		} // end for

		// Add the exitTo indexes of the currentLineProc into the procExitToIndexes
		// if the end can be reached from currentLine
		bool canReachEnd = checkCanExitProc(currentLine, v, true, true);
		if (canReachEnd) {
			Type::List::Line nextExitToIndexes = getProcExitToIndexes(currentLineProc);
			for (auto it = nextExitToIndexes.begin(); it != nextExitToIndexes.end(); it++) {
				if ( !Utilities::isKeyInMap_TypeType(exitToIndexesMap, *it)) {
					procExitToIndexes.push_back(*it);
					exitToIndexesMap.insert( std::make_pair(*it, true) );
				}
			}
		}
	}
	
	// If we got out without returning in the process then definitely we did not find any reachable call stmts to call back
	// to this proc,
	// BUT we may have calledToIndexes to check again!
	// NOTE: calledToIndexes are definitely the start of procs,
	// So check for call stmts that they call by using isReachable(calledToIndex, callLine, v, true, false)
	for (unsigned i = 0; i < calledToIndexes.size(); i++) {
		for (auto callLine = callList.begin(); callLine != callList.end(); callLine++) {
			Type::Index::Proc calledProc = getCalledByLine(*callLine);
			bool isTheCallWeNeed = calledProc == xProc;
			Type::Index::Proc procStart = getProcStartEnd(calledProc).first;
			if ( !Utilities::isKeyInMap_TypeType(exitToIndexesMap, procStart)) {
				// Only bother about unique indexes
				// Check if the callLine can be reached from the calledTo index
				Type::Index::Line calledTo = calledToIndexes.at(i);
				bool canReach = isReachable(calledTo, *callLine, v, true, false);
				if (canReach) {
					if (isTheCallWeNeed) {
						// immediately we are done!
						return true;
					}
					// Add the called proc procStart to the calledTo since we can reach the callLine
					calledToIndexes.push_back(procStart);
					exitToIndexesMap.insert( std::make_pair(procStart, true) );
				}
			}
		}
	}

	// Now we are definitely unable to get back to line y :(
	return false;
}

// Checks if there is a route by going out of the procedure from x using reachable
// call stmts and exit points, in order to reach y.
// Definition: x has an out route to y which does not modify v iff
// hasLoopBackRoute(x,y,v) which will only work if x and y are in the same procs, OR...
// 1. x and y are in different procs
// 2. there exists some control path starting from x by using reachable call stmts and exit points
//		from x in order to reach y.
bool PKB::hasOutRoute(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v) {
	Type::Index::Proc xProc = getProcIndexOfLine(x);
	Type::Index::Proc yProc = getProcIndexOfLine(y);
	if (xProc == yProc) {
		// when x and y are in the same proc, it is the same as finding a loop back route
		return hasLoopBackRoute(x, y, v);
	}

	// Here, x and y are in different procs
	// So we need to find some control path starting from x by using reachable call stmts and exit points.
	
	// First, exit points. If we can get to the end of the proc without walls, then we can use the exit points
	bool canReachEnd = checkCanExitProc(x, v, false, true);

	Type::List::Line procExitToIndexes;
	std::map<Type::Index::Line, bool> exitToIndexesMap;
	if (canReachEnd) {
		// can use proc exit to indexes only if can reach end
		procExitToIndexes = getProcExitToIndexes(xProc);
	}
	procExitToIndexes.push_back(x);
	exitToIndexesMap.insert( std::make_pair(x, true) );
	const Type::List::Line& callList = getLinesByEntity(Type::Entity::CALL_LINE_ENTITY);
	Type::List::Line calledToIndexes;
	// Next, we add all the call stmts which x can reach by loop back
	for (unsigned int i = 0; i < procExitToIndexes.size(); i++) {
		Type::Index::Line currentLine = procExitToIndexes.at(i);
		Type::Index::Proc currentLineProc = getProcIndexOfLine(currentLine);
		// Check and see if we can reach y
		if (currentLineProc == yProc) { 
			// Same proc, check if the currentLine can reach y
			if (currentLine == y) {
				// reached!
				return true;
			} else if (isLineAWall(currentLine, v)) {
				// currentLine is a wall, but if it is a IF line we may
				// still reach y!
				if (isLineEntity(currentLine, Type::Entity::IF_LINE_ENTITY) 
					&& hasLoopBackRoute(currentLine, y, v)) {
						return true;
				}
			} else if (hasLoopBackRoute(currentLine, y, v)) {
				// Can reach!
				return true;
			}
		}
		for (unsigned int j = 0; j < callList.size(); j++) {
			Type::Index::Line callLine = callList.at(j);
			Type::Index::Proc calledProc = getCalledByLine(callLine);
			bool isReachable;
			Type::Index::Proc callLineProc = getProcIndexOfLine(callLine);
			if (callLineProc != currentLineProc) {
				// Not in same proc, definitely not reachable
				isReachable = false;
			} else if (currentLine == callLine) {
				// In same proc
				// If we are already on the call line, we are on it so it is reachable.
				isReachable = true;
			} else {
				// In same proc but not on the call line.
				if (currentLine != x && isLineAWall(currentLine, v)) {
					// Here we are not on the call line, and the currentLine is a wall that is not x
					// However, if currentLine is a IF line,
					// we may still be able to reach the call line.
					if ( (isLineEntity(currentLine, Type::Entity::IF_LINE_ENTITY)) 
						&& hasLoopBackRoute(currentLine, callLine, v)) {
							isReachable = true;
					} else {
						// CALL or ASSIGN wall, which are true walls
						isReachable = false;
					}
				} else {
					// Here we are not on the call line, and the currentLine is NOT a wall
					isReachable = hasLoopBackRoute(currentLine, callLine, v);
				}
			}
			// isReachable has been set
			if (isReachable) {
				// Can reach the call line, so add the start of the called proc to the calledToIndexes
				Type::Index::Line startOfCalledProc = getProcStartEnd(calledProc).first;
				if ( !Utilities::isKeyInMap_TypeType(exitToIndexesMap, startOfCalledProc)) {
					calledToIndexes.push_back(startOfCalledProc);
					exitToIndexesMap.insert( std::make_pair(startOfCalledProc, true) );
				}
			}
		}
		// Add the exitTo indexes of the currentLineProc into the procExitToIndexes
		// if the end can be reached from currentLine
		bool canReachEnd = checkCanExitProc(currentLine, v, true, true);
		
		if (canReachEnd) {
			Type::List::Line nextExitToIndexes = getProcExitToIndexes(currentLineProc);
			for (auto it = nextExitToIndexes.begin(); it != nextExitToIndexes.end(); it++) {
				if ( !Utilities::isKeyInMap_TypeType(exitToIndexesMap, *it)) {
					procExitToIndexes.push_back(*it);
					exitToIndexesMap.insert( std::make_pair(*it, true) );
				}
			}
		}
	}

	// If we got out without returning in the process then definitely we did not find any reachable call stmts to call back
	// to this proc,
	// BUT we may have calledToIndexes to check again!
	// NOTE: calledToIndexes are definitely the start of procs,
	// So check for call stmts that they call by using isReachable(calledToIndex, callLine, v, true, false)
	for (unsigned i = 0; i < calledToIndexes.size(); i++) {
		for (auto callLine = callList.begin(); callLine != callList.end(); callLine++) {
			Type::Index::Proc calledProc = getCalledByLine(*callLine);
			Type::Index::Proc procStart = getProcStartEnd(calledProc).first;
			Type::Index::Line calledTo = calledToIndexes.at(i);
			Type::Index::Proc calledToProc = getProcIndexOfLine(calledTo);
			// Check and see if we can reach y
			if (calledToProc == yProc) { 
				// Same proc, check if the currentLine can reach y
				if (calledTo == y) {
					// reached!
					return true;
				} else if (isLineAWall(calledTo, v)) {
					// calledTo is a wall, but if it is a IF line we may
					// still reach y!
					if (isLineEntity(calledTo, Type::Entity::IF_LINE_ENTITY) 
						&& hasLoopBackRoute(calledTo, y, v)) {
							return true;
					}
				} else if (hasLoopBackRoute(calledTo, y, v)) {
					// Can reach!
					return true;
				}
			}
			if ( !Utilities::isKeyInMap_TypeType(exitToIndexesMap, procStart)) {
				// Only bother about unique indexes
				// Check if the callLine can be reached from the calledTo index
				bool canReach = isReachable(calledTo, *callLine, v, true, false);
				if (canReach) {
					// Add the called proc procStart to the calledTo since we can reach the callLine
					calledToIndexes.push_back(procStart);
					exitToIndexesMap.insert( std::make_pair(procStart, true) );
				}
			}
		}
	}

	// Now we are definitely unable to get back to line y :(
	return false;
}

// For debugging: prints out all the (x,y,v) triplets that satisfy hasDirectRouteInProc(x,y,v)
void PKB::printAllHasDirectRouteInProc() {
	Type::List::Line lineList = getLines();
	Type::List::Var varList = getVarIndices();
	unsigned int count = 0;
	for (auto it = lineList.begin(); it != lineList.end(); it++) {
		for (auto it2 = lineList.begin(); it2 != lineList.end(); it2++) {
			for (auto it3 = varList.begin(); it3 != varList.end(); it3++) {
				if (hasDirectRouteInProc(*it, *it2, *it3)) {
					count++;
					cout << "hasDirectRouteInProc(" << *it << "," << *it2 << "," << getVarName(*it3) << ")\n";
				}
			}
		}
	}
	cout << "Total no. of directRouteInProcs = " << count << endl;
}

// For debugging: prints out all the (x,y,v) triplets that satisfy isReachable(x,y,v)
void PKB::printAllIsReachable(bool includeX, bool includeY) {
	Type::List::Line lineList = getLines();
	Type::List::Var varList = getVarIndices();
	unsigned int count = 0;
	for (auto it = lineList.begin(); it != lineList.end(); it++) {
		for (auto it2 = lineList.begin(); it2 != lineList.end(); it2++) {
			for (auto it3 = varList.begin(); it3 != varList.end(); it3++) {
				if (isReachable(*it, *it2, *it3, includeX, includeY)) {
					count++;
					cout << "isReachable(" << *it << "," << *it2 << "," << getVarName(*it3) << ", " << includeX << ", " << includeY << ")\n";
				}
			}
		}
	}
	cout << "Total no. of isReachables = " << count << endl;
}

// For debugging: prints out all the (x,y,v) triplets that satisfy hasLoopBackRoute(x,y,v)
void PKB::printAllHasLoopBackRoute() {
	Type::List::Line lineList = getLines();
	Type::List::Var varList = getVarIndices();
	unsigned int count = 0;
	for (auto it = lineList.begin(); it != lineList.end(); it++) {
		for (auto it2 = lineList.begin(); it2 != lineList.end(); it2++) {
			for (auto it3 = varList.begin(); it3 != varList.end(); it3++) {
				if (hasLoopBackRoute(*it, *it2, *it3)) {
					count++;
					cout << "hasLoopBackRoute(" << *it << "," << *it2 << "," << getVarName(*it3) << ")\n";
				}
			}
		}
	}
	cout << "Total no. of loopBackRoutes = " << count << endl;
}

// For debugging: prints out all the (x,y,v) triplets that satisfy hasOutRoute(x,y,v)
void PKB::printAllHasOutRoute() {
	Type::List::Line lineList = getLines();
	Type::List::Var varList = getVarIndices();
	unsigned int count = 0;
	for (auto it = lineList.begin(); it != lineList.end(); it++) {
		for (auto it2 = lineList.begin(); it2 != lineList.end(); it2++) {
			for (auto it3 = varList.begin(); it3 != varList.end(); it3++) {
				if (hasOutRoute(*it, *it2, *it3)) {
					count++;
					cout << "hasOutRoute(" << *it << "," << *it2 << "," << getVarName(*it3) << ")\n";
				}
			}
		}
	}

	cout << "Total no. of outRoutes = " << count << endl;

	for (auto it = lineList.begin(); it != lineList.end(); it++) {
		for (auto it2 = lineList.begin(); it2 != lineList.end(); it2++) {
			if (hasOutRoute(*it, *it2, 0)) {
				cout << "nextBIP*(" << *it << "," << *it2 << ")\n";
			}
		}
	}
}

/// return the list of lines that the given line affectBip indirectly
Type::List::Line& PKB::getAffectBipStar(Type::Index::Line line){
	Type::List::Line *temp = new Type::List::Line();
	if ( !isLineExists(line)) {
		return *temp;
	}
	return getAffectsBip(false, true, line);;
}

/// return the list of indirectly affectedBip lines by the given line
Type::List::Line& PKB::getAffectedBipStar(Type::Index::Line line){
	Type::List::Line *temp = new Type::List::Line();
	if ( !isLineExists(line)) {
		return *temp;
	}

	return getAffectsBip(true, true, line);;
}
/// check if the given line 1 indirectly affectBip the given line 2
bool PKB::isAffectBipStar(Type::Index::Line firstLine, Type::Index::Line secondLine){
	if ( !isLineExists(firstLine) || !isLineExists(secondLine)) {
		return false;
	}

	Type::List::Line assigns = getPossibleAffectBipLinesFrom(true, firstLine);
	Type::Set::Line assignsToCheck = Type::Set::Line(assigns.begin(), assigns.end());
	Type::List::Line result;
	bool affectResult = recurAffectsBip(false, false, true, firstLine, secondLine, assignsToCheck, result); 
	return affectResult;
}

Type::List::Line& PKB::getAffectsBip(bool isFirst, bool isStar, Type::Index::Line line){
	Type::List::Line* resultList = new Type::List::Line();

	if(!isLineExists(line) 
		|| !isLineEntity(line, Type::Entity::ASSIGNMENT_LINE_ENTITY)){
			return *resultList;
	}

	Type::List::Line assigns = getPossibleAffectBipLinesFrom(isFirst, line);
	Type::Set::Line assignsToCheck = Type::Set::Line(assigns.begin(), assigns.end());

	Type::Index::Line first = -1;
	Type::Index::Line second = -1;

	if(isFirst){
		first = line;
	}else{
		second = line;
	}

	recurAffectsBip(true, isFirst, isStar, first, second, assignsToCheck, *resultList);
	return *resultList;
}

const Type::List::Line& PKB::getPossibleAffectBipLinesFrom(bool isFirst, Type::Index::Line line){
	Type::List::Line* lines = new Type::List::Line();
		
	if(!isLineExists(line)){
		return *lines;
	}

	// get all assignment lines
	Type::List::Line assigns = getLinesByEntity(Type::Entity::ASSIGNMENT_LINE_ENTITY);
	Type::Index::Line tmpLine;
	bool nextBipStar;

	for(unsigned int h=0; h<assigns.size(); h++){
		tmpLine = assigns.at(h);
		
		if(isFirst){
			nextBipStar = isNextBipStar(line, tmpLine);
		}else{
			nextBipStar = isNextBipStar(tmpLine, line);
		}

		if(nextBipStar){
			lines->push_back(tmpLine);
		}
	}

	return *lines;
}

bool PKB::recurAffectsBip(bool isGet, bool isFirst, bool isStar, Type::Index::Line first, Type::Index::Line second, 
	Type::Set::Line& assigns, Type::List::Line& results){
		// this function cannot solve isAffectsBip()
		assert( isGet || isStar);

		Type::Index::Line tmpLine, recurLine, lineGiven;
		Type::List::Line recurList;
		bool affectBip;

		Type::Set::Line::iterator it = assigns.begin();
		while (it != assigns.end()){
			tmpLine = *it;

			// check for getAffectBip( first, _ ) or isAffectsBip( first, _ )
			if(isFirst || !isGet){
				affectBip = isAffectBip(first, tmpLine);
				lineGiven = first;
			} else {
				affectBip = isAffectBip(tmpLine, second);
				lineGiven = second;
			}

			if(affectBip){
				// record the lines for AffectsBip
				results.push_back(tmpLine);

				// record the lines to recur for AffectsBip*
				if(isStar){
					recurList.push_back(tmpLine);
				}

				// since there tmpline already checked for isAffectsBip relationship
				// and isAffectsBip = TRUE, so it should be included in the next search
				it = assigns.erase(it);
			}else{
				it++;
			}
		}

		bool result = false;
		// when there is at least one line to recur
		for(unsigned int h=0; h<recurList.size() && isStar && !result;h++){
			recurLine = recurList.at(h);

			if(isGet){
				if(isFirst && lineGiven != recurLine){
					// getAffectsBip*( recurLine , _ )
					recurAffectsBip(isGet, isFirst, isStar, recurLine, second, assigns, results);
				}else{
					// getAffectsBip*( _ , recurLine )
					recurAffectsBip(isGet, isFirst, isStar, first, recurLine, assigns, results);
				}
			}else{
				// isAffectsBip*( recurLine , second )
				if(recurLine == second){
					// isAffectsBip*( recurLine , second ) is found
					result = true;
				}else if (lineGiven != recurLine){
					// recur on checking isAffects*( recurLine , second);
					result = recurAffectsBip(isGet, isFirst, isStar, recurLine, second, assigns, results);
				}

				// stop recurring assignment lines when an isAffects* is found
				if(result){
					break;
				}
			}
		}

		if(isGet){
			// getAffectsBip( _ , second) or getAffectsBip( first, _ ) 
			// or getAffectsBip*( _ , second ) or getAffectsBip*( first , _ )
			// will always reach here
			return true;
		}else{
			// isAffectsBip( first, second) or isAffectsBip*(first, second)
			// will always reach here
			return result;
		}
}

/****************Follow**************/

//the second Type::Index::Line follows the first Type::Index::Line
void PKB::setFollows(Type::Index::Line s1,Type::Index::Line s2){
	if(Utilities::isValidLineIndex(s1) && Utilities::isValidLineIndex(s2)){
		myFollowsTable.setFollows(s1,s2);
	}
}

//get the Type::Index::Line which follows the given Type::Index::Line
//If none is found return -1.
Type::Index::Line PKB::getFollows(Type::Index::Line s){
	if (!Utilities::isValidLineIndex(s)) {
		return -1;
	}
	return myFollowsTable.getFollows(s);
}

//get the Type::Index::Line which is followed by the given Type::Index::Line
//If none is found return -1.
Type::Index::Line PKB::getFollowedBy(Type::Index::Line s){
	if (!Utilities::isValidLineIndex(s)) {
		return -1;
	}
	return myFollowsTable.getFollowedBy(s);
}

//return true if the second Type::Index::Line follows the first Type::Index::Line
bool PKB::isFollows(Type::Index::Line s1,Type::Index::Line s2){
	if (!Utilities::isValidLineIndex(s1) || !Utilities::isValidLineIndex(s2)) {
		return false;
	}
	return myFollowsTable.isFollows(s1,s2);
}

//return a set of lines which the given line follows all the lines in the set directly or indirectly
Type::List::Line PKB::getFollowStar(Type::Index::Line s){
	if (!Utilities::isValidLineIndex(s)) {
		return Type::List::Line();
	}
	Type::List::Line  result;
	Type::Index::Line follower = myFollowsTable.getFollows(s);
	while (follower != -1){
		result.push_back(follower);
		follower = myFollowsTable.getFollows(follower);
	}
	return result;
}

//return a set of lines which has the given line entity type and follows the given line  directly or indirectly
// e.g. Follows(1,2), Follows(2,3), Follows(3,4) where 4 is while statement-> getFollowsStar(1, WHILE_LINE_ENTITY) = {4}
//if none is found, return an empty vector
Type::List::Line PKB::getFollowStar(Type::Index::Line s, Type::Entity::Line rType){
	if (!Utilities::isValidLineIndex(s)) {
		return Type::List::Line();
	}
	Type::List::Line  result;
	Type::Index::Line follower = myFollowsTable.getFollows(s);
	while (follower != -1){
		if (isLineEntity(follower, rType)){
			result.push_back(follower);
		}
		follower = myFollowsTable.getFollows(follower);
	}
	return result;
}

//return a set of lines which all the lines in the set followed by the given line directly or indirectly
Type::List::Line  PKB::getFollowedByStar(Type::Index::Line s){
	if (!Utilities::isValidLineIndex(s)) {
		return Type::List::Line();
	}
	Type::List::Line  result;
	Type::Index::Line followedBy = myFollowsTable.getFollowedBy(s);
	while (followedBy != -1){
		result.push_back(followedBy);
		followedBy = myFollowsTable.getFollowedBy(followedBy);
	}
	return result;
}

// return a set of lines which has the given line entity type and is followed by the given line directly or indirectly
// e.g. Follows(1,2), Follows(2,3), Follows(3,5) where 2, 3 are while statement -> getFollowedByStar(5, WHILE_LINE_ENTITY) = {2,3} 
//if none is found, return an empty vector
Type::List::Line PKB::getFollowedByStar(Type::Index::Line s, Type::Entity::Line rType){
	if (!Utilities::isValidLineIndex(s)) {
		return Type::List::Line();
	}
	Type::List::Line  result;
	Type::Index::Line followedBy = myFollowsTable.getFollowedBy(s);
	while (followedBy != -1){
		if (isLineEntity(followedBy, rType)){
			result.push_back(followedBy);
		}
		followedBy = myFollowsTable.getFollowedBy(followedBy);
	}
	return result;
}

//return true if the seconde Type::Index::Line follows the first Type::Index::Line directly or indirectly
bool PKB::isFollowStar(Type::Index::Line s1,Type::Index::Line s2){
	if (!Utilities::isValidLineIndex(s1) || !Utilities::isValidLineIndex(s2)) {
		return false;
	}
	if (PKB::myFollowStarBitMapFlag){
		return PKB::myFollowStarBitMap.at(s1).at(s2);
	}else{
		Type::List::Line  followers;
		followers = PKB::getFollowStar(s1);
		return Utilities::isExistInList(followers,s2);
	}
}

bool PKB::setFollowBitMap(Type::Map::Bit CBM){
	return myFollowsTable.setFollowsBitMap(CBM);
}

bool PKB::isFollowBitMapSet(){
	return myFollowsTable.isBitMapSet();
}

bool PKB::setFollowStarBitMap(Type::Map::Bit CBM){
	if (CBM.empty()){
		return PKB::myFollowStarBitMapFlag;
	}
	int parentsize = CBM.size();
	int childsize = CBM.at(0).size();
	PKB::myFollowStarBitMap.resize(parentsize, vector<bool>(childsize,false));
	for (int i=0; i<parentsize;i++){
		for (int j=0; j<childsize;j++){
			PKB::myFollowStarBitMap.at(i).at(j) = CBM.at(i).at(j);
		}
	}
	PKB::myFollowStarBitMapFlag = true;
	return PKB::myFollowStarBitMapFlag;
	//return PKB::setBitMap(CBM,PKB::myFollowStarBitMap,'f');
}
bool PKB::isFollowStarBitMapSet(){
	return PKB::myFollowStarBitMapFlag;
}

/****************Parent**************/

//Set the first Type::Index::Line as the parent of the second Type::Index::Line
void PKB::setParent(Type::Index::Line p, Type::Index::Line c){
	if(Utilities::isValidLineIndex(p) && Utilities::isValidLineIndex(c)){
		myParentTable.setParent(p,c);
	}
}

//return a set of Type::Index::Line which are the direct child of the given Type::Index::Line
Type::List::Line  PKB::getChild(Type::Index::Line p){
	if (!Utilities::isValidLineIndex(p)) {
		return Type::List::Line();
	}
	return myParentTable.getChild(p);
}

//return a set of Type::Index::Line which are of the given LineEntity Type and are the direct child of the given Type::Index::Line
//if none is found, return an empty vector
Type::List::Line PKB::getChild(Type::Index::Line p, Type::Entity::Line cType){
	if (!Utilities::isValidLineIndex(p)) {
		return Type::List::Line();
	}
	Type::List::Line child = myParentTable.getChild(p);
	Type::List::Line filtedChild = filterLineIndexByLineEntityType(child, cType);
	return filtedChild;
}

//return the direct parent of the given Type::Index::Line
//if none is found, return -1
Type::Index::Line PKB::getParent(Type::Index::Line c){
	if (!Utilities::isValidLineIndex(c)) {
		return -1;
	}
	return myParentTable.getParent(c);
}

//return true if given Type::Index::Line has parent
bool PKB::hasParent(Type::Index::Line c){
	if (!Utilities::isValidLineIndex(c)) {
		return false;
	}
	return myParentTable.hasParent(c);
}

//return true if given Type::Index::Line has parent and this parent has the given line entity type
bool PKB::hasParent(Type::Index::Line c, Type::Entity::Line pType){
	if (!Utilities::isValidLineIndex(c)) {
		return false;
	}else if(myParentTable.hasParent(c)){
		Type::Index::Line parent = myParentTable.getParent(c);
		return (isLineEntity(parent, pType));
	}else{
		return false;
	}
}

//return true if given Type::Index::Line has parent
bool PKB::hasChild(Type::Index::Line p){
	if (!Utilities::isValidLineIndex(p)) {
		return false;
	}
	return myParentTable.hasChild(p);
}

//return true if given Type::Index::Line has child which this child has the given line entity type
bool PKB::hasChild(Type::Index::Line p, Type::Entity::Line cType){
	if (!Utilities::isValidLineIndex(p)) {
		return false;
	}else if(myParentTable.hasChild(p)){
		Type::List::Line child = PKB::getChild(p,cType);
		return !child.empty();
	}else{
		return false;
	}
}

//return true if the first Type::Index::Line is the direct Parent of the second Type::Index::Line
bool PKB::isParent(Type::Index::Line p, Type::Index::Line c){
	if (!Utilities::isValidLineIndex(p) || !Utilities::isValidLineIndex(c)) {
		return false;
	}
	return myParentTable.isParent(p,c);
}

//an iterative method to get the direct and indirect child of p
void PKB::getChildStarHelper(Type::Index::Line p, Type::List::Line  *childTotal){
	Type::List::Line::iterator iter;
	Type::List::Line  child = PKB::getChild(p);
	for (iter = child.begin(); iter != child.end(); iter++){
		childTotal->push_back(*iter);
		getChildStarHelper(*iter,childTotal);
	}
}
//return a set of Type::Index::Line which are the direct or indirect child of the given Type::Index::Line p
Type::List::Line  PKB::getChildStar(Type::Index::Line p){
	if (!Utilities::isValidLineIndex(p)) {
		return Type::List::Line();
	}
	Type::List::Line  childTotal;
	getChildStarHelper(p,&childTotal);
	return childTotal;
}

//return a set of Type::Index::Line which are of the given LineEntity type and are the direct or indirect child of the given Type::Index::Line
//if none is found, return an empty vector
Type::List::Line PKB::getChildStar(Type::Index::Line p, Type::Entity::Line cType){
	Type::List::Line  childTotal = PKB::getChildStar(p);
	Type::List::Line filtedChild = PKB::filterLineIndexByLineEntityType(childTotal, cType);
	return filtedChild;
}


//return a set of Type::Index::Line which are the direct or indirect parent of the given Type::Index::Line
Type::List::Line  PKB::getParentStar(Type::Index::Line c){
	if (!Utilities::isValidLineIndex(c)) {
		return Type::List::Line();
	}
	Type::List::Line  parentTotal;
	while (PKB::getParent(c)!=-1){
		parentTotal.push_back(getParent(c));
		c = getParent(c);
	}
	return parentTotal;
}

//return a set of Type::Index::Line which are of the given LineEntity type and are the direct or indirect parent of the given Type::Index::Line
//if none is found, return an empty vector
Type::List::Line PKB::getParentStar(Type::Index::Line c, Type::Entity::Line pType){
	Type::List::Line parentTotal = PKB::getParentStar(c);
	Type::List::Line filtedParent = PKB::filterLineIndexByLineEntityType(parentTotal, pType);
	return filtedParent;
}

//return true if the first Type::Index::Line is the direct or indirect Parent of the second Type::Index::Line
bool PKB::isParentStar(Type::Index::Line p, Type::Index::Line c){
	if (!Utilities::isValidLineIndex(p) || !Utilities::isValidLineIndex(c)) {
		return false;
	}
	if (PKB::myParentStarBitMapFlag){
		return PKB::myParentStarBitMap.at(p).at(c);
	}else{
		Type::List::Line  parent;
		parent = PKB::getParentStar(c);
		return Utilities::isExistInList(parent,p);
	}
}
bool PKB::setParentBitMap(Type::Map::Bit CBM){
	return myParentTable.setParentBitMap(CBM);
}
bool PKB::isParentBitMapSet(){
	return myParentTable.isBitMapSet();
}
bool PKB::setParentStarBitMap(Type::Map::Bit CBM){
	if (CBM.empty()){
		return PKB::myParentStarBitMapFlag;
	}
	int parentsize = CBM.size();
	int childsize = CBM.at(0).size();
	PKB::myParentStarBitMap.resize(parentsize, vector<bool>(childsize,false));
	for (int i=0; i<parentsize;i++){
		for (int j=0; j<childsize;j++){
			PKB::myParentStarBitMap.at(i).at(j) = CBM.at(i).at(j);
		}
	}
	PKB::myParentStarBitMapFlag = true;
	return PKB::myParentStarBitMapFlag;
	//return PKB::setBitMap(CBM,PKB::myParentStarBitMap,'p');
}
bool PKB::isParentStarBitMapSet(){
	return PKB::myParentStarBitMapFlag;
}

/**********Call**************/
//Set the first Proc calls the second Proc, with the specific line index who calls the second proc.
//return false, if not set successfully
bool PKB::setCalls(Type::Index::Proc callerProc, Type::Index::Line callerLine, Type::Index::Proc calledProc){
	return myCallsTable.setCalls(callerProc, callerLine, calledProc);
}

//return a list of all procedure indexes called by a specified index
//if none, return an empty vector
//eg. Calls(1,2) Calls(1,3) ---> getCalledBy(1) will return 2,3
Type::List::Proc PKB::getCalledBy(Type::Index::Proc callerProc){
	return myCallsTable.getCalledBy(callerProc);
}

//return a list of all procedure indexes called by a specified lineIndex
//if none, return -1
//eg. Calls(1,2) and line 5 in procefure 1 calls procedure 2.---> getCalledByLine(5) will return 2
Type::Index::Proc PKB::getCalledByLine(Type::Index::Line callerLine){
	return myCallsTable.getCalledByLine(callerLine);
}

//return a list of all procedure indexes that call a specified index
//if none, return an empty vectore
//eg. Calls(1,3) Calls(2,3) ---> getCallerOf(3) will return 1,2
Type::List::Proc PKB::getCallerOf(Type::Index::Proc calledProc){
	return myCallsTable.getCallerOf(calledProc);	
}

//return a list of all line indexes that call a specified procIndex
//if none, return an empty vector
//eg. Calls(1,3) Calls(2,3) where line 5, line 8 in procedure 1 and line 9 in procedure 2 call procedure 3 ---> getCallerLineOf(3) will return 5,8,9
Type::List::Line PKB::getCallerLineOf(Type::Index::Proc calledProc){
	return myCallsTable.getCallerLineOf(calledProc);
}

//return true if the first Proc calls the second Proc
bool PKB::isCalls(Type::Index::Proc callerProc, Type::Index::Proc calledProc){
	return myCallsTable.isCalls(callerProc, calledProc);
}


//Only for procedure index(need to take care of recursion call)
void PKB::getCallStarHelper(int p, vector<int> *childTotal, vector<int> (PKB::*innerFunction)(int), PKB* mypkb){
	vector<int>::iterator iter;
	vector<int>  child = (mypkb->*innerFunction)(p);
	for (iter = child.begin(); iter != child.end(); iter++){
		//if this child is not explored
		if (!Utilities::isExistInList(*childTotal,*iter)){
			childTotal->push_back(*iter);
			getCallStarHelper(*iter,childTotal,innerFunction, mypkb);
		}
	}
}
Type::List::Line PKB::getCallStmtsInProc(Type::Index::Proc p){
	if (!Utilities::isValidProcIndex(p)){
		return Type::List::Line();
	}else{
		return myCallsTable.getCallStmtOfProc(p);
	}
}

//Call* relation
//return a list of all procedure indexes called by a specified procIndex directly or indirectly
//if none, return an empty vector
//eg. Calls*(1,2) Calls*(1,3) ---> getCalledByStar(1) will return 2,3
Type::List::Proc PKB::getCalledByStar(Type::Index::Proc callerProc){
	if (!Utilities::isValidProcIndex(callerProc)){
		return Type::List::Proc();
	}
	Type::List::Proc calledProcTotal;
	getCallStarHelper(callerProc, &calledProcTotal, &PKB::getCalledBy, this);
	return calledProcTotal;
}

//return a list of all procedure indexes called by a specified lineIndex directly or indirectly
//if none, return an empty list
//eg. Calls*(1,2) and line 5 in procefure 1 calls procedure 2 directly or indirectly.---> getCalledByLine(5) will return 2
Type::List::Proc PKB::getCalledByLineStar(Type::Index::Line callerLine){
	if (!Utilities::isValidLineIndex(callerLine)){
		return Type::List::Proc();
	}
	Type::List::Proc calledByLineProcTotal;
	Type::Index::Proc calledByLineProc = getCalledByLine(callerLine);
	if (calledByLineProc == -1){
		return vector<Type::Index::Proc>();
	}else{
		calledByLineProcTotal.push_back(calledByLineProc);
		getCallStarHelper(calledByLineProc, &calledByLineProcTotal, &PKB::getCalledBy, this);
		return calledByLineProcTotal;
	}
}

//return a list of all procedure indexes that call a specified procIndex directly or indirectly
//if none, return an empty vector
//eg. Calls*(1,3) Calls*(2,3) ---> getCallerOfStar(3) will return 1,2
Type::List::Proc PKB::getCallerOfStar(Type::Index::Proc calledProc){
	if (!Utilities::isValidProcIndex(calledProc)){
		return Type::List::Proc();
	}
	Type::List::Proc callerProcTotal;
	getCallStarHelper(calledProc, &callerProcTotal, &PKB::getCallerOf, this);
	return callerProcTotal;
}



void PKB::getCallerLineOfStarHelper(Type::Index::Proc calledProc, vector<int> *callerLineTotal, vector<int> *checkedProc){
	Type::List::Line callerLineFirstLayer = getCallerLineOf(calledProc);
	callerLineTotal->insert(callerLineTotal->end(),callerLineFirstLayer.begin(),callerLineFirstLayer.end());
	Type::List::Proc callerProc = getCallerOf(calledProc);
	for (vector<int>::iterator it = callerProc.begin(); it!=callerProc.end(); ++it){
		if (!Utilities::isExistInList(*checkedProc,*it)){
			checkedProc->push_back(*it);
			getCallerLineOfStarHelper(*it,callerLineTotal,checkedProc);
		}
	}
}

//return a list of all line indexes that call a specified procIndex directly or indirecly
//if none, return an empty vector
//eg. Calls*(1,3) Calls*(2,3) where line 5, line 8 in procedure 1 and line 9 in procedure 2 call procedure 3 directly or indirectly ---> getCallerLineOf(3) will return 5,8,9
Type::List::Line PKB::getCallerLineOfStar(Type::Index::Proc calledProc){
	if (!Utilities::isValidProcIndex(calledProc)){
		return Type::List::Line();
	}
	Type::List::Line callerLineTotal;
	Type::List::Proc checkedProc;
	getCallerLineOfStarHelper(calledProc, &callerLineTotal, &checkedProc);
	return callerLineTotal;
}

////return true if the first Proc calls the second Proc directly or indirectly
bool PKB::isCallsStar(Type::Index::Proc callerProc, Type::Index::Proc calledProc){
	if (!Utilities::isValidProcIndex(callerProc) || !Utilities::isValidProcIndex(calledProc)) {
		return false;
	}
	if (PKB::myCallStarBitMapFlag){
		return PKB::myCallStarBitMap.at(callerProc).at(calledProc);
	}else{
		Type::List::Line  calledProcList;
		calledProcList = PKB::getCalledByStar(callerProc);
		return Utilities::isExistInList(calledProcList,calledProc);
	}
}

//return true if the bitmap for calls is set correctly
bool PKB::setCallsBitMap(Type::Map::Bit callsBitMap){
	return myCallsTable.setCallsBitMap(callsBitMap);
}
bool PKB::setCallStarBitMap(Type::Map::Bit CBM){
	if (CBM.empty()){
		return PKB::myCallStarBitMapFlag;
	}
	int parentsize = CBM.size();
	int childsize = CBM.at(0).size();
	PKB::myCallStarBitMap.resize(parentsize, vector<bool>(childsize,false));
	for (int i=0; i<parentsize;i++){
		for (int j=0; j<childsize;j++){
			PKB::myCallStarBitMap.at(i).at(j) = CBM.at(i).at(j);
		}
	}
	PKB::myCallStarBitMapFlag = true;
	return PKB::myCallStarBitMapFlag;
}
bool PKB::isCallStarBitMapSet(){
	return PKB::myCallStarBitMapFlag;
}

// Returns true if the given proc, starting from the first line, has no possible path through which
// it does not modify the given var, and false if it has at least one such possible path.
// A proc is a wall if it has a wall line in its direct stmt list.
bool PKB::isProcAWall(const Type::Index::Proc proc, const Type::Index::Var var) {
	assert (isProcExistInProcTable(proc));
	if ( !isVarExists(var)) {
		return false;
	}
	// Here, we are ensured that proc and var exists.

	// If the proc does not even modify the var then it is immediately NOT a wall
	if ( !isProcModifies(proc, var)) {
		return false;
	}
	std::string procVarString = getProcName(proc) + " " + getVarName(var);
	// If the proc exists in the isProcAWallMap, we have checked if it is a wall for this variable before.
	if (Utilities::isKeyInMap_TypeType(isProcAWallMap, procVarString)) {
		return isProcAWallMap.at(procVarString);
	}

	// Here, we are ensured that proc has at least one line modifying var,
	// so we check if ANY of the lines in its direct stmt list is a wall.
	Type::Pair::StartEnd procStartEnd = getProcStartEnd(proc);
	int procStart = procStartEnd.first;
	int procEnd = procStartEnd.second;
	int currentLine = procStart;
	Type::Entity::Line currentLineEntity;
	do {
		if (isLineAWall(currentLine, var)) {
			// Found a wall line!
			isProcAWallMap.insert( std::make_pair(procVarString, true) );
			return true;
		} else {
			// Did not find a wall line, so have to continue checking if there is a nextModified from an appropriate line.
			// Note: we use nextModified for speed.
			currentLineEntity = getLineEntityByLine(currentLine);
			if (currentLineEntity == Type::Entity::IF_LINE_ENTITY) {
				// when the line is an if, we need to go to the last line of the else stmt list
				currentLine = getLastOfIf(currentLine).at(1);
			} 
			// Now find the next modified
			currentLine = myModifyTable.getNextModified(currentLine, var);
			
			// Now, check if the line is out of the proc (might be 0 from getNextModified, or might exceed the last line of the proc from
			// getting the last of if + 1
			// If it is out of the proc then this proc is not a wall, return false.
			if (currentLine < procStart || currentLine > procEnd) {
				isProcAWallMap.insert( std::make_pair(procVarString, false) );
				return false;
			}
		}
	} while (true);
}

// Returns true if the given line 'definitely modifies' the given var, and false otherwise.
// Here, 'definitely modifies' means the following:
// For ASSIGN: if it modifies the var.
// For CALL: if the procedure called by this line is a wall.
// For WHILE: can always exit the while immdeiately, so it can't be a wall.
// For IF: if there is a wall line in BOTH its then and else direct stmt lists.
bool PKB::isLineAWall(const Type::Index::Line line, const Type::Index::Var var) {
	assert (line > 0);
	if ( !isVarExists(var)) {
		return false;
	}
	// Here, we are ensured that line is greater than 0 and the variable exists

	Type::Entity::Line lineEntity = getLineEntityByLine(line);
	
	// Following only used for IF line
	Type::Index::Line startOfThen;
	Type::Index::Line lastOfThen;
	Type::Index::Line startOfElse;
	Type::Index::Line lastOfElse;
	bool isThenWall;
	bool isElseWall;
	
	// Used for IF and WHILE line
	Type::Index::Line checkLine;

	bool isWall = false;
	switch (lineEntity) {
	case Type::Entity::ASSIGNMENT_LINE_ENTITY:
		isWall = isLineModifies(line, var);
		break;
	case Type::Entity::CALL_LINE_ENTITY:
		isWall = isProcAWall(getCalledByLine(line), var);
		break;
	case Type::Entity::WHILE_LINE_ENTITY:
		isWall = false;
		//lastLineOfWhile = getLastOfWhile(line);
		//checkLine = line;
		//// Check all the lines directly within this while stmt list
		//do {
		//	checkLine = myModifyTable.getNextModified(checkLine, var);
		//	if (checkLine < line || checkLine > lastLineOfWhile) {
		//		// The checkLine is not in this while line, so this while line is NOT a wall
		//		isWall = false;
		//		break;
		//	} else {
		//		// The checkLine is within this while line stmt list, so check if it is a wall line
		//		if (isLineAWall(checkLine, var)) {
		//			// Is a wall, can break
		//			isWall = true;
		//			break;
		//		} else {
		//			// Is not a wall, must set the checkLine correctly before next loop iteration
		//			// Only tricky ones are WHILE and IF checkLines,
		//			// and for WHILE, just set the checkLine to the last line of while,
		//			// and for IF, just set the checkLine to the last line of the else stmt list
		//			if (lineEntity == Type::Entity::WHILE_LINE_ENTITY) {
		//				checkLine = lastLineOfWhile;
		//			} else if (lineEntity == Type::Entity::IF_LINE_ENTITY) {
		//				checkLine = getLastOfIf(checkLine).at(1);
		//			}
		//		}
		//	}
		//} while (true);
		break;
	case Type::Entity::IF_LINE_ENTITY:
		isThenWall = false;
		isElseWall = false;
		startOfThen = line + 1;
		lastOfThen = getLastOfIf(line).at(0);
		startOfElse = lastOfThen + 1; 
		lastOfElse = getLastOfIf(line).at(1);
		// Check if both stmt lists contain walls
		// First, check the then stmt list
		checkLine = startOfThen;
		if (isLineAWall(checkLine, var)) {
			isThenWall = true;
		} else {
			do {
				if (getLineEntityByLine(checkLine) == Type::Entity::IF_LINE_ENTITY) {
					// No need to go into it, but instead go to the end of it 
					checkLine = getLastOfIf(checkLine).at(1);
				}
				checkLine = myModifyTable.getNextModified(checkLine, var);
				if (checkLine < startOfThen || checkLine > lastOfThen) {
					// Out of the then stmt list
					isThenWall = false;
					break;
				} else {
					// In the then stmt list still
					if (isLineAWall(checkLine, var)) {
						isThenWall = true;
						break;
					}
				}
			} while (true);
		}
		// Then, check the else stmt list
		checkLine = startOfElse;
		if (isLineAWall(checkLine, var)) {
			isElseWall = true;
		} else {
			do {
				if (getLineEntityByLine(checkLine) == Type::Entity::IF_LINE_ENTITY) {
					// No need to go into it, but instead go to the end of it 
					checkLine = getLastOfIf(checkLine).at(1);
				}
				checkLine = myModifyTable.getNextModified(checkLine, var);
				if (checkLine < startOfElse || checkLine > lastOfElse) {
					// Out of the then stmt list
					isElseWall = false;
					break;
				} else {
					// In the then stmt list still
					if (isLineAWall(checkLine, var)) {
						isElseWall = true;
						break;
					}
				}
			} while (true);
		}

		if (isThenWall && isElseWall) {
			isWall = true;
		}
		break;
	default: // Should not be here!
		cout << "PKB::isLineAWall(" << line << ", " << getVarName(var) << ") got a bad entity and is in a branch it should not be in!\n";
		assert (false);
		break;
	}
	return isWall;
}

// Returns the commonIf line of x and y using the getCommon function in PKB.
// At the same time, also sets the hasCommonIf, xInThen, and yInThen boolean values.
Type::Index::Line PKB::findCommonIf(Type::Index::Line x, Type::Index::Line y, 
	bool* hasCommonIfPtr, bool* xInThenPtr, bool* yInThenPtr) {
		Type::Index::Line xParent = getParent(x);
		Type::Index::Line yParent = getParent(y);
		if (xParent <= 0 || yParent <= 0) {
			*hasCommonIfPtr = false;
			*xInThenPtr = false;
			*yInThenPtr = false;
			return -1;
		} else {
			Type::Index::Line commonIf = getCommon(Type::Entity::IF_LINE_ENTITY, xParent, yParent);
			if (commonIf <= 0) {
				// No common if
				*hasCommonIfPtr = false;
				*xInThenPtr = false;
				*yInThenPtr = false;
				return -1;
			} else {
				// Has common if
				*hasCommonIfPtr = true;
				Type::Index::Line lastOfThen = getLastOfIf(commonIf).at(0);
				*xInThenPtr = x > commonIf && x <= lastOfThen;
				*yInThenPtr = y > commonIf && y <= lastOfThen;
				return commonIf;
			}
		}
}

// Returns the commonWhile line of x and y using the getCommon function in PKB.
// At the same time, also sets the hasCommonWhile boolean value.
Type::Index::Line PKB::findCommonWhile(Type::Index::Line x, Type::Index::Line y, bool* hasCommonWhilePtr) {
	Type::Index::Line xParent;
	Type::Index::Line yParent;
	bool isXContainer = isLineEntity(x, Type::Entity::WHILE_LINE_ENTITY) || isLineEntity(x, Type::Entity::IF_LINE_ENTITY);
	bool isYContainer = isLineEntity(y, Type::Entity::WHILE_LINE_ENTITY) || isLineEntity(y, Type::Entity::IF_LINE_ENTITY);
	if (x == y) {
		// If on the same line, always go up a level
		xParent = getParent(x);
		yParent = getParent(y);
	} else {
		// Otherwise, x or y might be the common while themselves,
		// so use themselves for common while finding if they are containers
		if (isXContainer) {
			xParent = x;
		} else {
			xParent = getParent(x);
		}
		if (isYContainer) {
			yParent = y;
		} else {
			yParent = getParent(y);
		}
	}

	if (xParent <= 0 || yParent <= 0) {
		*hasCommonWhilePtr = false;
		return -1;
	} else {
		Type::Index::Line commonWhile = getCommon(Type::Entity::WHILE_LINE_ENTITY, xParent, yParent);
		if (commonWhile <= 0) {
			// No common while
			*hasCommonWhilePtr = false;
			return -1;
		} else {
			// Has common while
			*hasCommonWhilePtr = true;
			return commonWhile;
		}
	}
}

// Function for debugging isProcAWall
void PKB::printAllWallProcs() {
	Type::List::Proc procList = getProcIndices();
	Type::List::Var varList = getVarIndices();
	for (auto procIter = procList.begin(); procIter != procList.end(); procIter++) {
		for (auto varIter = varList.begin(); varIter != varList.end(); varIter++) {
			if (isProcAWall(*procIter, *varIter)) {
				cout << "isProcAWall(" << getProcName(*procIter) << ", " << getVarName(*varIter) << ") is TRUE\n";
			}
		}
	}
}

// Function for debugging isLineAWall
void PKB::printAllWallLines() {
	Type::List::Line lineList = getLines();
	Type::List::Var varList = getVarIndices();
	for (auto lineIter = lineList.begin(); lineIter != lineList.end(); lineIter++) {
		for (auto varIter = varList.begin(); varIter != varList.end(); varIter++) {
			if (isLineAWall(*lineIter, *varIter)) {
				cout << "isLineAWall(" << *lineIter << ", " << getVarName(*varIter) << ") is TRUE\n";
			}
		}
	}
}

// Function for debugging getProcExitToIndexes
void PKB::printAllProcExitToIndexes() {
	Type::List::Proc procList = getProcIndices();
	for (auto procIter = procList.begin(); procIter != procList.end(); procIter++) {
		Type::List::Line exitToIndexes = getProcExitToIndexes(*procIter);
		for (auto exitToIter = exitToIndexes.begin(); exitToIter != exitToIndexes.end(); exitToIter++) {
			cout << "procExitsToIndex(" << getProcName(*procIter) << ", " << *exitToIter << ")\n";
		}
	}
}

// Gets the line indices to which the given procedure may return to (if it is called by another procedure).
// May be empty if this procedure does not exit to and lines.
Type::List::Line PKB::getProcExitToIndexes(Type::Index::Proc proc) {
	assert (isProcExistInProcTable(proc));
	// Here, we are ensured that the proc exists.

	if (Utilities::isKeyInMap_TypeType(procExitToIndexesMap, proc)) {
		// Already know what line indexes the proc exits to, so return it immediately.
		return procExitToIndexesMap.at(proc);
	} 

	// Here, we don't know what line indexes the proc exits to, so let's find it!
	std::vector<Type::Index::Line> procExitToIndexesList;
	std::map<Type::Index::Line, bool> indexesAddedMap; // to ensure uniqueness
	// This proc can only exit to line indexes that are successors to the lines that call it.
	// If the lines that call it have no successors, then we need to get the lines to which the procedure containing
	// that call stmt exits to.
	Type::List::Line callLines = getCallerLineOf(proc);
	for (auto callIter = callLines.begin(); callIter != callLines.end(); callIter++) {
		Type::List::Line successorList = getSuccessorNext(*callIter);
		if (successorList.empty()) {
			// No successors, so we have to get the lines to which the procedure containing the call stmt exits to
			successorList = getProcExitToIndexes(getProcIndexOfLine(*callIter));
		}
		for (auto successorIter = successorList.begin(); successorIter != successorList.end(); successorIter++) {
			if ( !Utilities::isKeyInMap_TypeType(indexesAddedMap, *successorIter)) {
				procExitToIndexesList.push_back(*successorIter);
				indexesAddedMap.insert( std::make_pair(*successorIter, true) );
			}
		}
	}

	procExitToIndexesMap.insert( std::make_pair(proc, procExitToIndexesList) );

	return procExitToIndexesList;
}

// Returns true if the line exists in the pkb.
bool PKB::isLineExists(Type::Index::Line line) {
	return myEntityTable.isLineExistsInEntity(line);
}

/*****Yude's method for Pattern matching******/

//Yude's method
Type::List::Line PKB::getLineIndexesForPattern(PatternType patternType, Type::Index::Var varRefIndex, 
	TreeNode* middleSubtreeRootToMatch, TreeNode* rightSubtreeRootToMatch, bool isPartialMiddle, bool isPartialRight) {
		Type::List::Line matchedProgLines; // to be returned

		//cout << "PKB: " << "getLineIndexesForPattern(" << patternType << ", " << varRefIndex << ", " << middleSubtreeRootToMatch << ", " << rightSubtreeRootToMatch << ", " << isPartialMiddle << ", " << isPartialRight << ")" << endl;
		// Preprocess arguments
		Type::Entity::Line lineEntityType = patternTypeToLineEntityType(patternType);
		if (lineEntityType == Type::Entity::INVALID_LINE_ENTITY) {
			// invalid, so just return empty vector immediately
			return Type::List::Line();
		}
		if (varRefIndex < 0) {
			// invalid, so just return empty vector immediately
			return Type::List::Line();
		}

		TreeNode* leftSubtreeRootToMatch = createTreeNode(AST_VAR, varRefIndex); 

		Type::List::Line matchPatternLines = getLinesByEntity(lineEntityType);
		//cout << endl;
		//cout << "PKB: " << "matchPatternLines size: " << matchPatternLines.size() << endl;
		for (unsigned int i=0; i<matchPatternLines.size(); i++){
			bool isMatch = false;

			Type::Index::Line lineIndex  = matchPatternLines.at(i);
			TreeNode* mPatternNodePointer = myNodeTable.getNodeByLine(lineIndex);

			//cout << "PKB: " << "Starting the pattern matching for line index: " << lineIndex << endl;
			//cout << "PKB: " << "Number of children for line index " << lineIndex << ": " << mPatternNodePointer->getNumberOfChildren() << endl;
			// We only match pattern for ASSIGN, WHILE, and IF, which have 2, 2, and 3 children respectively.
			if (mPatternNodePointer->getNumberOfChildren() == 2) {
				// ASSIGN, WHILE
				TreeNode* varRefNode = mPatternNodePointer->getChild().at(0);
				TreeNode* exprNode = mPatternNodePointer->getChild().at(1);
				//cout << "PKB: " << "Line index " << lineIndex << ": " << "Matching varRefNode (" << varRefNode->getContent() << ") against leftSubtreeRootToMatch(" << leftSubtreeRootToMatch->getContent() << ")" << endl;
				isMatch = matchSubtreePerfectly(varRefNode, leftSubtreeRootToMatch); // always match the variable node perfectly
				if (varRefIndex == 0) {
					// pattern a (_,"x+...+y") does not matter whether the left subtree matches
					isMatch = true;
				}
				if (!isMatch) {
					// variable didn't match, continue with next lineIndex
					continue;
				}

				if (isPartialMiddle) {
					// partial matching
					isMatch = isMatch && matchSubtreePartially(exprNode, middleSubtreeRootToMatch);
				} else {
					// perfect matching
					isMatch = isMatch && matchSubtreePerfectly(exprNode, middleSubtreeRootToMatch);
				}
				if (!isMatch) {
					// not matched, continue with lineIndex
					//cout << "PKB: did not match line index " << lineIndex << endl;
					continue;
				} else {
					// MATCHED!
					//cout << "PKB: MATCHED line index " << lineIndex << endl;
					matchedProgLines.push_back(lineIndex);
				}
			} else if (mPatternNodePointer->getNumberOfChildren() == 3) {
				// IF
				TreeNode* varRefNode = mPatternNodePointer->getChild().at(0);
				TreeNode* thenNode = mPatternNodePointer->getChild().at(1);
				TreeNode* elseNode = mPatternNodePointer->getChild().at(2);

				// Match variable node
				isMatch = matchSubtreePerfectly(varRefNode, leftSubtreeRootToMatch);
				if (varRefIndex == 0) {
					// pattern a (_,"x+...+y") does not matter whether the left subtree matches
					isMatch = true;
				}
				if (!isMatch) {
					// not matched, continue with next lineIndex
					continue;
				}

				// Match then node
				if (isPartialMiddle) {
					// partial matching
					isMatch = isMatch && matchSubtreePartially(thenNode, middleSubtreeRootToMatch);
				} else {
					// perfect matching
					isMatch = isMatch && matchSubtreePerfectly(thenNode, middleSubtreeRootToMatch);
				}
				if (!isMatch) {
					// not matched, continue with next lineIndex
					continue;
				}

				// Match else node
				if (isPartialRight) {
					// partial matching
					isMatch = isMatch && matchSubtreePartially(elseNode, rightSubtreeRootToMatch);
				} else {
					// perfect matching
					isMatch = isMatch && matchSubtreePerfectly(elseNode, rightSubtreeRootToMatch);
				}
				if (!isMatch) {
					// not matched, continue with next lineIndex
					continue;
				} else {
					// MATCH!
					matchedProgLines.push_back(lineIndex);
				}
			} else {
				// INVALID
				continue;
			}

		}
		return matchedProgLines;
}

//Yude's method
bool PKB::matchSubtreePerfectly(TreeNode* rootMainTree, TreeNode* rootSubtree) {
	if (rootMainTree == NULL) {
		// we do not match anything with a NULL!
		//cout << "PKB: " << "matchSubtreePerfectly: rootMainTree == NULL" << endl;
		//cout << "PKB: " << "matchSubtreePerfectly: returns false" << endl;
		return false;
	}
	if (rootSubtree == NULL) {
		// since this is perfect matching, matching a NULL to something is FALSE!
		//cout << "PKB: " << "matchSubtreePerfectly: rootSubtree == NULL" << endl;
		//cout << "PKB: " << "matchSubtreePerfectly: returns false" << endl;
		return false;
	}

	// From here on, rootMainTree and rootSubTree are both NON-NULL.

	// At each node, check for 4 things to ensure they match:
	// 1. Node type
	// 2. Content
	// 3. Number of children
	// 4. The children themselves

	// Get the 4 things from rootMainTree
	TreeNodeType mainNodeType = rootMainTree->getNodeType();
	int mainContent = rootMainTree->getContent();
	int mainNumOfChildren = rootMainTree->getNumberOfChildren();
	std::vector<TreeNode*> mainChildren = rootMainTree->getChild();
	// Get the 4 things from rootSubtree
	TreeNodeType subNodeType = rootSubtree->getNodeType();
	int subContent = rootSubtree->getContent();
	int subNumOfChildren = rootSubtree->getNumberOfChildren();
	std::vector<TreeNode*> subChildren = rootSubtree->getChild();
	//cout << "PKB: " << "Matching mainNodeType " << mainNodeType << " against subNodeType " << subNodeType << endl;
	//cout << "PKB: " << "Matching mainContent " << mainContent << " against subContent " << subContent << endl;
	//cout << "PKB: " << "Matching mainNumOfChildren " << mainNumOfChildren << " against subNumOfChildren " << subNumOfChildren << endl;
	//cout << endl;
	// If any don't match, immediately return false
	if (mainNodeType != subNodeType) {
		return false;
	}
	if (mainContent != subContent) {
		return false;
	}
	if (mainNumOfChildren != subNumOfChildren) {
		return false;
	}
	for (unsigned int i = 0; i < mainChildren.size(); i++) {
		TreeNode* mainChild = mainChildren.at(i);
		TreeNode* subChild = subChildren.at(i);
		if ( !matchSubtreePerfectly(mainChild, subChild) ) {
			return false;
		}
	}
	return true;
}

//Yude's method
bool PKB::matchSubtreePartially(TreeNode* rootMainTree, TreeNode* rootSubtree) {
	if (rootMainTree == NULL) {
		// we do not match anything with a NULL!
		//cout << "PKB: " << "matchSubtreePartially: rootMaintree == NULL" << endl;
		//cout << "PKB: " << "matchSubtreePartially: returns false" << endl;
		return false;
	}
	if (rootSubtree == NULL) {
		// since this is partial matching, matching a NULL to something is TRUE!
		//cout << "PKB: " << "matchSubtreePartially: rootSubtree == NULL" << endl;
		//cout << "PKB: " << "matchSubtreePartially: returns true" << endl;
		return true;
	}

	// From here on, rootMainTree and rootSubTree are both NON-NULL.

	// At each node, check for 4 things to ensure they match:
	// 1. Node type
	// 2. Content
	// 3. Number of children (*unless the rootSubTree is at 0 children, meaning nothing else to be matched beneath it*)
	// 4. The children themselves
	// Get the 4 things from rootMainTree
	TreeNodeType mainNodeType = rootMainTree->getNodeType();
	int mainContent = rootMainTree->getContent();
	int mainNumOfChildren = rootMainTree->getNumberOfChildren();
	std::vector<TreeNode*> mainChildren = rootMainTree->getChild();
	// Get the 4 things from rootSubtree
	TreeNodeType subNodeType = rootSubtree->getNodeType();
	int subContent = rootSubtree->getContent();
	int subNumOfChildren = rootSubtree->getNumberOfChildren();
	std::vector<TreeNode*> subChildren = rootSubtree->getChild();
	//cout << "PKB: " << "Matching mainNodeType " << mainNodeType << " against subNodeType " << subNodeType << endl;
	//cout << "PKB: " << "Matching mainContent " << mainContent << " against subContent " << subContent << endl;
	//cout << "PKB: " << "Matching mainNumOfChildren " << mainNumOfChildren << " against subNumOfChildren " << subNumOfChildren << endl;
	bool isMatch = true;
	if (mainNodeType != subNodeType) {
		isMatch = false;
	}
	if (mainContent != subContent) {
		isMatch = false;
	}
	if (mainNumOfChildren < subNumOfChildren) {
		isMatch = false;
	}
	if (isMatch) {
		for (unsigned int i = 0; i < subChildren.size(); i++) {
			TreeNode* mainChild = mainChildren.at(i);
			TreeNode* subChild = subChildren.at(i);
			// Use without recursion for correctness
			if ( !matchSubtreePartiallyWithoutRecursion(mainChild, subChild) ) {
				isMatch = false;
				break;
			}
		}
	}
	if (!isMatch) {
		for (unsigned int i = 0; i < mainChildren.size(); i++) {
			TreeNode* mainChild = mainChildren.at(i);
			// Recursively try and find a match
			if ( matchSubtreePartially(mainChild, rootSubtree) ) {
				return true;
			}
		}
		// couldn't find a partial match at all!
		return false;
	} else {
		// already found a match
		return true;
	}
}

//Yude's method
bool PKB::matchSubtreePartiallyWithoutRecursion(TreeNode* mainChildRoot, TreeNode* subChildRoot) {
	if (mainChildRoot == NULL) {
		// we do not match anything with a NULL!
		//cout << "PKB: " << "matchSubtreePartiallyWithoutRecursion: mainChildRoot == NULL" << endl;
		//cout << "PKB: " << "matchSubtreePartiallyWithoutRecursion: returns false" << endl;
		return false;
	}
	if (subChildRoot == NULL) {
		// since this is not matching roots, NULL is not an acceptable match
		//cout << "PKB: " << "matchSubtreePartiallyWithoutRecursion: subChildRoot == NULL" << endl;
		//cout << "PKB: " << "matchSubtreePartiallyWithoutRecursion: returns false" << endl;
		return true;
	}

	// From here on, rootMainTree and rootSubTree are both NON-NULL.

	// At each node, check for 4 things to ensure they match:
	// 1. Node type
	// 2. Content
	// 3. Number of children (*unless the rootSubTree is at 0 children, meaning nothing else to be matched beneath it*)
	// 4. The children themselves
	// Get the 4 things from rootMainTree
	TreeNodeType mainNodeType = mainChildRoot->getNodeType();
	int mainContent = mainChildRoot->getContent();
	int mainNumOfChildren = mainChildRoot->getNumberOfChildren();
	std::vector<TreeNode*> mainChildren = mainChildRoot->getChild();
	// Get the 4 things from rootSubtree
	TreeNodeType subNodeType = subChildRoot->getNodeType();
	int subContent = subChildRoot->getContent();
	int subNumOfChildren = subChildRoot->getNumberOfChildren();
	std::vector<TreeNode*> subChildren = subChildRoot->getChild();

	if (mainNodeType != subNodeType) {
		return false;
	}
	if (mainContent != subContent) {
		return false;
	}
	if (mainNumOfChildren < subNumOfChildren) {
		return false;
	}
	for (unsigned int i = 0; i < subChildren.size(); i++) {
		TreeNode* mainChild = mainChildren.at(i);
		TreeNode* subChild = subChildren.at(i);
		// Use without recursion for correctness
		if ( !matchSubtreePartiallyWithoutRecursion(mainChild, subChild) ) {
			return false;
		}
	}
	return true;
}

TreeNodeType PKB::lineEntityTypeToTreeNodeType(Type::Entity::Line lineEntity) {
	switch (lineEntity) {
	case Type::Entity::ASSIGNMENT_LINE_ENTITY:
		return AST_ASSIGN;
	case Type::Entity::IF_LINE_ENTITY:
		return AST_IF;
	case Type::Entity::WHILE_LINE_ENTITY:
		return AST_WHILE;
	default: 
		return AST_INVALID_TYPE;
	}
}